반응형
알고리즘 분류 : BFS
BFS 탐색을 통해 두 동전을 보드에서 떨어뜨리는 최단 거리를 구하면 된다. 동전 두 개가 동시에 움직이므로, 방문 여부를 확인할 배열을 4차원으로 설정하는 것이 좋다. '구슬 탈출'과 비슷한 문제다.
- 방문 여부를 확인하고 거리를 저장할 배열 dist를 4차원으로 선언한다. (동전1 X좌표, 동전1 Y좌표, 동전2 X좌표, 동전2 Y좌표)
- 보드를 입력받을 때 가장자리를 0으로 비워두고, 입력받는다. 즉, N*M 사이즈를 (N+2)*(M+2) 사이즈로 확장한다.
- 동전 두 개 중 하나가, 가장자리(인덱스 0, N+1 또는 0, M+1)인 경우 BFS 탐색을 중지하고 거리를 출력한다.
- 동전이 둘 다 가장자리로 갔다면, 둘 다 떨어뜨릴 수 없으므로 무시한다.
- 동전이 벽(#)에 부딪혔을 경우, 동전 둘 다 부딪쳤다면 이동이 불가능하다.
- 동전이 하나만 벽에 부딪혔을 경우, 하나는 그대로 움직이고 하나는 이동하기 전으로 되돌려 놓는다.
- 이동 거리가 10을 넘는다면, 버튼을 10번 넘게 누른 것이므로 BFS 탐색을 중지한다.
C++ 소스코드
#include <cstdio> #include <queue> using namespace std; struct coin { int x, y, a, b; // (x, y) : coin 1, (a, b) coin 2 }; int n, m; char board[22][22]; int dist[22][22][22][22]; queue<coin> q; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; bool escape(int &x, int &y) { return x < 1 || x > n || y < 1 || y > m; } bool wall(int &x, int &y) { return board[x][y] == '#'; } void bfs() { while (!q.empty()) { int x = q.front().x, y = q.front().y; int a = q.front().a, b = q.front().b; q.pop(); if (dist[x][y][a][b] > 10) break; if (escape(x, y) ^ escape(a, b)) { printf("%d\n", dist[x][y][a][b]); // One coin escaped. return; } for (int i=0; i<4; i++) { int nx = x+dx[i], ny = y+dy[i]; int na = a+dx[i], nb = b+dy[i]; if (escape(nx, ny) && escape(na, nb)) continue; // Both coins cannot escape. if (wall(nx, ny) && wall(na, nb)) continue; // Cannot pass the wall. if (wall(nx, ny)) nx = x, ny = y; else if (wall(na, nb)) na = a, nb = b; if (dist[nx][ny][na][nb]) continue; // Check a visit. q.push({nx, ny, na, nb}); dist[nx][ny][na][nb] = dist[x][y][a][b] + 1; } } printf("-1\n"); } int main() { int x = -1, y; scanf("%d %d", &n, &m); for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) { scanf("%1s", &board[i][j]); if (board[i][j] == 'o') { if (x == -1) x = i, y = j; else q.push({x, y, i, j}); } } } bfs(); return 0; }
Python 3 소스코드
from sys import stdin from collections import deque input = stdin.readline n, m = map(int, input().split()) board = ['0'*(m+2)] dist = [[[[0 for _ in range(m+2)] for _ in range(n+2)] for _ in range(m+2)] for _ in range(n+2)] q = deque() dx, dy = (-1, 0, 1, 0), (0, 1, 0, -1) def init(): for _ in range(n): board.append(list('0' + input().strip() + '0')) board.append(list('0'*(m+2))) x, y = -1, -1 for i in range(1, n+1): for j in range(1, m+1): if board[i][j] == 'o': if x == -1: x, y = i, j else: q.append((x, y, i, j)) return def escape(x, y): return x < 1 or x > n or y < 1 or y > m def wall(x, y): return board[x][y] == '#' def bfs(): while q: x, y, a, b = q.popleft() if dist[x][y][a][b] > 10: break if escape(x, y) ^ escape(a, b): print(dist[x][y][a][b]) return for i in range(4): nx, ny, na, nb = x+dx[i], y+dy[i], a+dx[i], b+dy[i] if escape(nx, ny) and escape(na, nb): continue if wall(nx, ny) and wall(na, nb): continue if wall(nx, ny): nx, ny = x, y elif wall(na, nb): na, nb = a, b if not dist[nx][ny][na][nb]: q.append((nx, ny, na, nb)) dist[nx][ny][na][nb] = dist[x][y][a][b]+1 print(-1) init() bfs()
참고
반응형