본문 바로가기

Programming

BOJ 3197 · 백조의 호수 알고리즘 분류 : BFS두 마리의 백조가 서로 만나는 데 걸리는 시간을 구하는 문제다. 백조는 빙판을 지날 수 없으며, 물로만 이동이 가능하다. 또한, 매일 물과 인접한 빙판이 녹아서 물로 변한다.입력으로 주어지는 맵의 범위가 최대 1500*1500이므로, 일반적인 BFS 방법으로는 시간 초과가 나온다. 여러 방법이 있겠지만, 아래 코드에서는 큐(Queue) 4개를 이용하는 방법을 사용했다.빙판이 물로 녹는 BFS와, 백조가 이동하는 BFS..
BOJ 2234 · 성곽 알고리즘 분류 : DFS성을 DFS 또는 BFS로 탐색하면서 3가지 값을 구해야 한다. 첫 번째는 성에 있는 방의 개수(A), 두 번째는 가장 큰 방의 넓이(B), 세 번째는 벽 하나를 제거해서 얻을 수 있는 가장 큰 방의 넓이(C)이다.입력으로 주어지는 맵을 DFS로 탐색한다.현재 칸을 (X, Y)라 할 때, check[X][Y]를 숫자 Z로 채운다.다음 칸으로 이동하기 전에 벽으로 막혀있는지 확인한다.벽을 확인하는 방법..
BOJ 12886 · 돌 그룹 알고리즘 분류 : BFSA, 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..
BOJ 5014 · 스타트링크 알고리즘 분류 : BFS엘리베이터를 이용하여 S 층부터 G 층까지 가는 최단 거리를 구하는 문제다. 이동은 U 버튼, D 버튼을 통해서만 가능하다.처음 층은 S 층부터 시작한다.현재 층을 X 층이라 하면, 다음 층은 X+U 층이거나, X-D 층이다.다음 층이 1 층에서 F 층 사이인지 확인한다.존재하는 층이거나 아직 방문하지 않은 층이라면 이동한다.G 층에 도착할 때까지 BFS 탐색을 진행하고, 도착하면 버튼 누른 횟수를 출력한다.도착하지 ..
BOJ 3184 · 양 알고리즘 분류 : BFS남아있는 양과 늑대의 수를 구하는 문제다. 특정 지역에서 양이 늑대보다 많으면 양만 살아남고, 그렇지 않으면 늑대만 살아남는다.각 영역은 울타리('#')로 둘러싸여 있으며, 영역 내부는 BFS를 통해 탐색한다.BFS 탐색을 하면서 양('o')의 수와 늑대('v')의 수를 센다.양이 늑대보다 많으면, 양만 살아남으므로 총 양의 수에 더한다.늑대가 양보다 많거나 같으면, 늑대만 살아남으므로 총 늑대의 수에 더한다.위의 과..
BOJ 15558 · 점프 게임 알고리즘 분류 : BFS점프 이동을 하면서 타일을 벗어나는 게임을 구현해야 한다. 점프 이동은 3가지이며, 한 번에 하나씩 진행하므로 BFS 탐색을 통해 해결할 수 있다.맵 좌표의 인덱스는 [왼쪽 또는 오른쪽 줄] [줄 번호] 이다. 왼쪽 줄은 0이고, 오른쪽 줄은 1이다.현재 좌표를 (X, Y)라 했을 때, 다음 좌표는 아래 3가지로 나타낼 수 있다.한 칸 앞으로 이동 : (X, Y+1)한 칸 뒤로 이동 : (X, Y-1)반대편 줄 점프 : (!X..
BOJ 1938 · 통나무 옮기기 알고리즘 분류 : BFSB 지점에 있는 통나무를 E 지점에 옮겨야 하는 문제다. 통나무의 길이는 3으로 고정되어 있고, 상하좌우 이동과 회전 이동이 가능하다. 길이가 3이라는 점과, 회전이 가능하다는 점이 굉장히 귀찮은 문제다. 특별한 아이디어가 안 떠올라서 다소 무식하게 코딩했다.통나무의 길이는 3으로 고정되므로, 가운데 정점을 이동 좌표로 삼는다.방문 체크와 이동 거리를 저장할 배열 dist를 3차원으로 선언한다. 인덱스는 [x 좌표] [y 좌표..
BOJ 2468 · 안전 영역 알고리즘 분류 : DFS물에 잠기지 않는 안전 영역의 최대 개수를 구하는 문제다. DFS 또는 BFS로 영역을 완전 탐색하면서, 영역의 개수를 셀 수 있다.입력으로 주어지는 값에서 가장 큰 값을 M이라 둔다.0부터 M-1까지 제한 높이 K를 올리면서 DFS를 돌린다.DFS로 탐색할 때, 잠기지 않는 영역(높이 K 초과)으로 이동한다. 이동하면서 방문 체크를 해둔다.아직 방문하지 않은 곳이면서 높이가 K보다 높다면, 다시 DFS로 탐색한다.N..
BOJ 2636 · 치즈 알고리즘 분류 : BFS치즈가 완전히 녹을 때까지 걸리는 시간을 구하는 문제다. BOJ 2638번 '치즈'와 유사하다. 자세한 내용은 이전 문제 참조.치즈 칸(1)에 외부 공기(1)가 인접한다면, 치즈를 녹인다.치즈를 녹일 때마다, 녹인 개수를 저장한다.C++ 소스코드#include <cstdio> #include <cstring> #include <queue> using namespace std; struct ch..
BOJ 2638 · 치즈 알고리즘 분류 : BFS치즈가 완전히 녹기까지 걸리는 시간을 구하는 문제다. 치즈는 한 칸에 놓이며, 인접한 칸에 외부 공기(0)가 2칸 이상 있다면, 녹는다. 내부 공기는 치즈에 영향을 주지 않으므로 유의해야 한다.입력으로 주어지는 맵은 가장자리가 항상 외부 공기(0)로 주어진다.따라서 (0, 0)이 항상 공기 칸이므로, BFS의 시작을 (0, 0)으로 한다.인접한 상하좌우 칸이 공기(0)라면, 이동한다.인접한 칸이 치즈(1)라면, 치즈를 1만큼 ..
BOJ 9376 · 탈옥 알고리즘 분류 : BFS두 죄수를 감옥에서 탈옥시킬 때, 열어야 하는 문의 최소 개수를 구하는 문제다. 죄수가 2명이고, 각 죄수는 문을 공유하며, 한 번만 문을 열어야 하기 때문에 까다롭다. 때문에 이 문제는 다른 방식으로 생각해야 한다.1. 첫 번째 죄수부터 출발하여 문을 여는 경우2. 두 번째 죄수부터 출발하여 문을 여는 경우위 두 가지로 나눠서 생각하면, 어떤 위치(X, Y)에서 함께 만나서 도착점(0, 0)으로 간다고 볼 수 있다. 도착점이..
BOJ 2251 · 물통 알고리즘 분류 : BFS부어서 만들 수 있는 물통의 경우의 수를 모두 만들고, 첫 번째 물통이 비어 있을 때 세 번째 물통에 담겨있는 물의 양을 구해야 한다. BFS 또는 DFS를 통해 물을 옮기면서 경우의 수를 만들 수 있다.물통이 총 3개이지만, 2개로 해결할 수 있다.물통에서 물을 옮길 때, 물의 양은 변하지 않으므로, 물통의 상태 변화를 첫 번째 물통과 두 번째 물통만 나타내도 된다.세 번째 물통에 있는 물의 양은 C-X-Y로 나타낼 수 있다..