전체 글
BOJ 2151 · 거울 설치
알고리즘 분류 : BFS 문에서 다른 문까지 빛으로 연결하기 위해 필요한 거울의 최소 개수를 구하는 문제다. 빛은 거울에서만 꺾이고, 거울은 45도 각도로 설치할 수 있다. 거울을 적절히 설치해서 문에서 문으로 빛을 연결해야 한다. 문('#')은 항상 2개만 주어지므로, 하나의 문을 시작점으로, 다른 하나의 문은 도착점으로 둔다.BFS 탐색을 하면서 다음 이동 좌표가 갈 수 있는 곳인지 확인한다.방문 체크와 거울 설치 횟수를 저장할 배열 dist를 3차원으로 선언한다.dist의 인덱스는 [X 좌표] [Y좌표] [이동 방향] 이다.만약 다음 이동 좌표가 맵의 밖이거나 벽('*')이라면, 이동할 수 없다.다음 이동 좌표가 빈 공간('.')이라면, 계속 이동한다.while 반복문을 통해 다음 이동이 가능한 위..
BOJ 3197 · 백조의 호수
알고리즘 분류 : BFS 두 마리의 백조가 서로 만나는 데 걸리는 시간을 구하는 문제다. 백조는 빙판을 지날 수 없으며, 물로만 이동이 가능하다. 또한, 매일 물과 인접한 빙판이 녹아서 물로 변한다.입력으로 주어지는 맵의 범위가 최대 1500*1500이므로, 일반적인 BFS 방법으로는 시간 초과가 나온다. 여러 방법이 있겠지만, 아래 코드에서는 큐(Queue) 4개를 이용하는 방법을 사용했다. 빙판이 물로 녹는 BFS와, 백조가 이동하는 BFS를 따로 나눈다.물을 위한 큐는 wq1, wq2가 있고, 백조를 위한 큐는 sq1, sq2가 있다.입력으로 주어지는 호수 맵에서 물('.')의 좌표를 wq1에 모두 넣는다.호수 맵에서 백조('L')의 좌표를 sq1에 하나 넣고, 다른 하나의 백조 위치는 도착 위치(..
BOJ 2234 · 성곽
알고리즘 분류 : DFS 성을 DFS로 탐색하면서 3가지 값을 구해야 한다. 첫 번째는 성에 있는 방의 개수(A), 두 번째는 가장 큰 방의 넓이(B), 세 번째는 벽 하나를 제거해서 얻을 수 있는 가장 큰 방의 넓이(C)이다. 입력으로 주어지는 맵을 DFS로 탐색한다.현재 칸을 (X, Y)라 할 때, check[X][Y]를 숫자 Z로 채운다.다음 칸으로 이동하기 전에 벽으로 막혀있는지 확인한다.벽을 확인하는 방법은 a[X][Y] & (1
BOJ 12886 · 돌 그룹
알고리즘 분류 : BFS A, B, C 돌 그룹에서 돌을 옮기면서 A == B == C 가 되도록 만드는 문제다. A, B, C의 합은 고정되어 있으므로, 두 개의 돌만 사용해도 된다. A + B + C의 합을 D라 하자.3개 돌의 수가 같아야 하므로, 3으로 나눴을 때 나누어떨어지지 않으면 만들 수 없는 경우이다.만약 3으로 나누어떨어지면, BFS 탐색을 진행한다.A와 B만 사용하면, C는 D-A-B로 나타낼 수 있다.(A, B), (A, C), (B, C)를 문제에 주어진 조건에 따라 서로 비교한다.돌 개수가 작은 쪽을 X, 큰 쪽을 Y라 하면, 다음 X 돌은 X+X개이고, 다음 Y 돌은 Y-X개가 된다.마지막 돌을 Z라 하면, Z는 D-X-Y로 나타낼 수 있다.중복된 경우를 제거하기 위해, (X, ..
BOJ 5014 · 스타트링크
알고리즘 분류 : BFS 엘리베이터를 이용하여 S 층부터 G 층까지 가는 최단 거리를 구하는 문제다. 이동은 U 버튼, D 버튼을 통해서만 가능하다. 처음 층은 S 층부터 시작한다.현재 층을 X 층이라 하면, 다음 층은 X+U 층이거나, X-D 층이다.다음 층이 1 층에서 F 층 사이인지 확인한다.존재하는 층이거나 아직 방문하지 않은 층이라면 이동한다.G 층에 도착할 때까지 BFS 탐색을 진행하고, 도착하면 버튼 누른 횟수를 출력한다.도착하지 못하면, "use the stairs"를 출력한다. C++ 소스코드 #include #include #include using namespace std; int F, S, G, U, D; int dist[1000001]; void bfs() { queue q; q...
BOJ 3184 · 양
알고리즘 분류 : BFS 남아있는 양과 늑대의 수를 구하는 문제다. 특정 지역에서 양이 늑대보다 많으면 양만 살아남고, 그렇지 않으면 늑대만 살아남는다. 각 영역은 울타리('#')로 둘러싸여 있으며, 영역 내부는 BFS를 통해 탐색한다.BFS 탐색을 하면서 양('o')의 수와 늑대('v')의 수를 센다.양이 늑대보다 많으면, 양만 살아남으므로 총 양의 수에 더한다.늑대가 양보다 많거나 같으면, 늑대만 살아남으므로 총 늑대의 수에 더한다.위의 과정을 모든 영역의 탐색이 끝날 때까지 진행한다. C++ 소스코드 #include #include #include using namespace std; int r, c, sheep, wolf; char a[251][251]; bool check[251][251]; c..
BOJ 15558 · 점프 게임
알고리즘 분류 : BFS 점프 이동을 하면서 타일을 벗어나는 게임을 구현해야 한다. 점프 이동은 3가지이며, 한 번에 하나씩 진행하므로 BFS 탐색을 통해 해결할 수 있다. 맵 좌표의 인덱스는 [왼쪽 또는 오른쪽 줄] [줄 번호] 이다. 왼쪽 줄은 0이고, 오른쪽 줄은 1이다.현재 좌표를 (X, Y)라 했을 때, 다음 좌표는 아래 3가지로 나타낼 수 있다.한 칸 앞으로 이동 : (X, Y+1)한 칸 뒤로 이동 : (X, Y-1)반대편 줄 점프 : (!X, Y+K)매초마다 타일이 한 칸씩 없어지는 것을 고려해야 한다.타일을 완전히 벗어나면, 즉 Y 인덱스가 N 이상이면 게임을 클리어 한 것이다. C++ 소스코드 #include #include #include using namespace std; int n..
BOJ 1938 · 통나무 옮기기
알고리즘 분류 : BFS B 지점에 있는 통나무를 E 지점에 옮겨야 하는 문제다. 통나무의 길이는 3으로 고정되어 있고, 상하좌우 이동과 회전 이동이 가능하다. 길이가 3이라는 점과, 회전이 가능하다는 점이 굉장히 귀찮은 문제다. 특별한 아이디어가 안 떠올라서 다소 무식하게 코딩했다. 통나무의 길이는 3으로 고정되므로, 가운데 정점을 이동 좌표로 삼는다.방문 체크와 이동 거리를 저장할 배열 dist를 3차원으로 선언한다. 인덱스는 [x 좌표] [y 좌표] [회전 방향] 이다.회전 방향은 가로일 때 0, 세로일 때 1이다.문제에 주어진 조건처럼, 이동할 때 다른 나무(1)이 없어야 한다.나무의 회전 방향에 따라 이동 가능한지 체크를 다르게 한다. C++ 소스코드 #include #include #inclu..