목록백준/bfs, dfs (47)
Study hard
www.acmicpc.net/problem/17135 [풀이] 문제에 나온 게임 순서대로 구현하였다. 1. 궁수 3명 배치: dfs를 이용하여 궁수 위치의 조합을 만들어 각 조합마다 게임을 진행하였다. 2. 적의 존재 여부 확인 및 적의 위치 저장(적이 존재하지 않으면 게임 끝) 3. 궁수마다 가장 가까운 적 찾아서 공격: 궁수와 가장 가까운 적을 찾고 그 적이 아직 공격받지 않았다면 공격할 수 있는 적의 수로 카운트 해주고 제외한다. 4. 적 아래로 한 칸 이동: 맵의 범위 넘어가면 제외 ※첫번째 줄부터 아래로 내려가면서 이동시키면 맵이 의도한 것과 다른 모양이 될 수 있으므로 마지막 줄부터 위로 올라가면서 이동시켜야 함!! #include #include #include //memset #includ..
www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net [풀이] dfs를 이용해서 풀 수 있는 문제였다. 오른쪽, 아래, 오른쪽 아래 대각선 방향으로만 움직이므로 파이프의 오른쪽 부분(이동방향쪽 한 칸)만 고려하면 된다. 일반적인 경로탐색에서 방향을 세 가지로 바꾸고 조건을 추가해주었다. 1. (N-1,N-1)에 도달하면 cnt++ 2. 가로, 세로 방향일 때 그 다음에 이동 가능한 방향인지 확인 3. 대각선 방향일 때 오른쪽, 아래, 오른..
www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net [풀이] dfs를 이용하여 풀 수 있는 문제였다. 괄호를 묶을 수 있는지 확인하는 것이 필요하다. 1. 괄호 묶을 수 있는지 확인(남은 개수 확인) 2. 현재까지 계산한 값과 다음 값 사이의 연산자 저장 3. 괄호를 묶는 경우. 괄호 묶은 연산자 계산하고 이전까지의 값과 계산 4. 괄호를 묶지 않는 경우. 현재 위치의 값과 이전까지의 값 계산 ※Max값 초기화할 때 습관적으로 -1 했다가 "틀렸..
https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net [풀이] 1. bfs사용 2. 사다리나 뱀이 있는 칸은 LorS배열에 해당 칸에 도착하면 어느 칸으로 이동하는지를 저장했다. 3. visited배열을 사용하여 한 번 방문했던 칸에 대해서는 다시 탐색하지 않도록 했다.(안 하면 메모리 초과!) #include #include using namespace std; struct Pos { int x; in..
https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net [풀이] bfs를 사용했다. 연산의 아스키 코드 순서대로 queue에 푸시해주었기 때문에 값이 t가 되면 바로 그때까지 했던 연산들을 출력하면 된다. set자료구조에 나온 값을 저장하여 같은 값에 대해 더 이상 탐색하지 않게 했다. /연산으로 인해 나오는 1은 처음 한 번만 나오면 되므로 set을 탐색하지 않고 boolean값으로 사용 여부를 체크했다. 사실 -는 쓸일이 없다. (t는 항상..
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net [풀이] 1. bfs를 사용하여 구역의 수를 구하였다. 2. 적록색약이 아닌 사람의 경우와 적록색약인 사람의 경우를 따로 함수로 구현했다. 3. bfs를 부르는 수 == 구역의 수 #include #include #include #include //memset using namespace std; struct Pos { int x, y; }; int N; int Map[100][100]; ..