BOJ
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..
BOJ 2468 · 안전 영역
알고리즘 분류 : DFS 물에 잠기지 않는 안전 영역의 최대 개수를 구하는 문제다. DFS로 영역을 완전 탐색하면서, 영역의 개수를 셀 수 있다. 입력으로 주어지는 값에서 가장 큰 값을 M이라 둔다.0부터 M-1까지 제한 높이 K를 올리면서 DFS를 돌린다.DFS로 탐색할 때, 잠기지 않는 영역(높이 K 초과)으로 이동한다. 이동하면서 방문 체크를 해둔다.아직 방문하지 않은 곳이면서 높이가 K보다 높다면, 다시 DFS로 탐색한다.N*N 사이즈의 맵을 모두 방문 체크했다면, 제한 높이를 1 올리고 다시 DFS를 반복한다. C++ 소스코드 #include #include using namespace std; struct cheese { int x, y; }; int n, m, ans; int a[100][1..
BOJ 2636 · 치즈
알고리즘 분류 : BFS 치즈가 완전히 녹을 때까지 걸리는 시간을 구하는 문제다. BOJ 2638번 '치즈'와 유사하다. 자세한 내용은 이전 문제 참조. 치즈 칸(1)에 외부 공기(1)가 인접한다면, 치즈를 녹인다.치즈를 녹일 때마다, 녹인 개수를 저장한다. C++ 소스코드 #include #include #include using namespace std; struct cheese { int x, y; }; int n, m, ans, piece; int a[100][100]; bool check[100][100]; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; void bfs() { memset(check, false, sizeof(check)); qu..
BOJ 2638 · 치즈
알고리즘 분류 : BFS 치즈가 완전히 녹기까지 걸리는 시간을 구하는 문제다. 치즈는 한 칸에 놓이며, 인접한 칸에 외부 공기(0)가 2칸 이상 있다면, 녹는다. 내부 공기는 치즈에 영향을 주지 않으므로 유의해야 한다. 입력으로 주어지는 맵은 가장자리가 항상 외부 공기(0)로 주어진다.따라서 (0, 0)이 항상 공기 칸이므로, BFS의 시작을 (0, 0)으로 한다.인접한 상하좌우 칸이 공기(0)라면, 이동한다.인접한 칸이 치즈(1)라면, 치즈를 1만큼 증가시킨다.BFS 탐색이 완료되면, 치즈는 1 이상의 값으로 된다.이때, 치즈 값이 3 이상이라면, 2번 이상 외부 공기에 닿은 것이므로, 치즈를 녹여서 공기 칸(0)으로 만든다.치즈 값이 2라면, 외부 공기에 한 번만 닿은 것이므로, 1로 다시 되돌려 놓..