반응형
알고리즘 분류 : BFS
두 죄수를 감옥에서 탈옥시킬 때, 열어야 하는 문의 최소 개수를 구하는 문제다. 죄수가 2명이고, 각 죄수는 문을 공유하며, 한 번만 문을 열어야 하기 때문에 까다롭다. 때문에 이 문제는 다른 방식으로 생각해야 한다.
1. 첫 번째 죄수부터 출발하여 문을 여는 경우
2. 두 번째 죄수부터 출발하여 문을 여는 경우
위 두 가지로 나눠서 생각하면, 어떤 위치(X, Y)에서 함께 만나서 도착점(0, 0)으로 간다고 볼 수 있다. 도착점이 (0, 0)인 이유는 맵의 가장자리로 탈출해야 하기 때문이다.
어떤 위치에서 도착점까지 가는 경우는 맵의 사이즈 만큼 존재한다. 이를 반대로 생각하면, 도착점(0, 0)에서 어떤 위치(X, Y)로 오는 경우로 볼 수 있다. 때문에, 이를 3가지의 경우로 볼 수 있다.
1. 첫 번째 죄수부터 출발하여 문을 여는 경우
2. 두 번째 죄수부터 출발하여 문을 여는 경우
3. 바깥쪽에서 출발하여 문을 여는 경우
위 3가지의 경우를 각각 더하고, 그중 가장 작은 값이 문을 여는 최솟값이 된다. 단, 문('#')은 한 번만 열기 때문에, 문에서 만나는 경우 2를 뺀다.
- 입력으로 주어지는 맵의 가장자리를 확장한다. 즉, H*W 사이즈의 맵을 (H+2)*(W+2) 사이즈로 확장한다.
- 가장자리는 빈 공간('.')으로 채운다.
- BFS를 총 3번 돌린다.
- 1. 감옥 밖(0, 0)에서 출발한다. BFS 탐색을 하면서 각 좌표에 문을 여는 횟수를 저장한다.
- 2. 첫 번째 죄수('$')에서 출발하여, 문을 여는 횟수를 저장한다.
- 3. 두 번째 죄수('$')에서 출발하여, 문을 여는 횟수를 저장한다.
- 위에서 저장한 3개의 배열을 모두 더하고, 그중 최솟값을 출력한다.
- 해당 좌표가 문('#')일 경우, 2를 뺀다.
C++ 소스코드
#include <cstdio> #include <cstring> #include <deque> using namespace std; struct prison { int x, y; }; int h, w; char a[102][102]; int dist[102][102][3]; deque<prison> dq; int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; void bfs() { dq.push_back({0, 0}); for (int k=0; k<3; k++) { int sx = dq.back().x, sy = dq.back().y; dq.pop_back(); deque<prison> q; q.push_back({sx, sy}); dist[sx][sy][k] = 0; while (!q.empty()) { int x = q.front().x, y = q.front().y; q.pop_front(); for (int i=0; i<4; i++) { int nx = x+dx[i], ny = y+dy[i]; if (nx < 0 || nx > h+1 || ny < 0 || ny > w+1) continue; if (dist[nx][ny][k] >= 0 || a[nx][ny] == '*') continue; if (a[nx][ny] == '.') { dist[nx][ny][k] = dist[x][y][k]; q.push_front({nx, ny}); } else if (a[nx][ny] == '#') { dist[nx][ny][k] = dist[x][y][k]+1; q.push_back({nx, ny}); } } } } } int main() { int t; scanf("%d", &t); while (t--) { memset(dist, -1, sizeof(dist)); scanf("%d %d", &h, &w); for (int i=0; i<h+2; i++) { for (int j=0; j<w+2; j++) { if (i == 0 || i == h+1 || j == 0 || j == w+1) a[i][j] = '.'; else scanf(" %1c", &a[i][j]); if (a[i][j] == '$') { a[i][j] = '.'; dq.push_back({i, j}); } } } bfs(); int ans = 1e9; for (int i=0; i<h+2; i++) { for (int j=0; j<w+2; j++) { if (a[i][j] == '*') continue; int k = dist[i][j][0] + dist[i][j][1] + dist[i][j][2]; if (a[i][j] == '#') k -= 2; if (ans > k) ans = k; } } printf("%d\n", ans); } return 0; }
Python 3 소스코드
from collections import deque from sys import stdin input = stdin.readline def bfs(sx, sy): dist = [[-1]*(w+2) for _ in range(h+2)] q = deque() q.append((sx, sy)) dist[sx][sy] = 0 while q: x, y = q.popleft() for dx, dy in (-1,0), (1,0), (0,-1), (0,1): nx, ny = x+dx, y+dy if nx < 0 or nx > h+1 or ny < 0 or ny > w+1: continue if dist[nx][ny] >= 0 or a[nx][ny] == '*': continue if a[nx][ny] == '.': dist[nx][ny] = dist[x][y] q.appendleft((nx, ny)) elif a[nx][ny] == '#': dist[nx][ny] = dist[x][y]+1 q.append((nx, ny)) return dist for _ in range(int(input())): h, w = map(int, input().split()) a = ['.'*(w+2)] for _ in range(h): a.append(list('.'+input().strip()+'.')) a.append(list('.'*(w+2))) dq = deque() for i in range(h+2): for j in range(w+2): if a[i][j] == '$': a[i][j] = '.' dq.append((i, j)) sx, sy = dq.pop() d1 = bfs(sx, sy) sx, sy = dq.pop() d2 = bfs(sx, sy) d3 = bfs(0, 0) ans = 1e9 for i in range(h+2): for j in range(w+2): if a[i][j] == '*': continue k = d1[i][j] + d2[i][j] + d3[i][j] if a[i][j] == '#': k -= 2 ans = min(ans, k) print(ans)
참고
- 백준 온라인 저지 : BOJ 9376
반응형