프로그래밍/알고리즘
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..
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..