반응형
알고리즘 분류 : BFS
구슬 탈출 세 번째 문제다. 이전 문제인 '구슬 탈출'과 '구슬 탈출 2'를 해결했으면, 조금만 추가해서 풀 수 있다. 자세한 내용은 이전 문제 참조. 이 문제가 구슬 탈출 시리즈 중에선 가장 까다롭다. 움직인 방향을 출력해야 하기 때문이다.
- 움직인 방향을 출력하기 위해서는 이전 위치를 저장하는 배열이 필요하다.
- 빨간 구슬 X, Y좌표, 파란 구슬 X, Y 좌표, 방향 정보를 가진 path 배열을 4차원으로 선언한다.
- 현재 위치에서 이전 위치와 이동 방향을 저장하고, 이 과정을 움직일 때마다 수행한다.
- 빨간 구슬이 구멍에 빠져서 답을 낼 수 있을 경우, 현재 위치에서 이전 위치로 되돌아가면서 방향을 저장한다.
- 방향을 마지막에서 처음으로 되돌아가는 것이므로, 역으로 출력한다.
C++ 소스코드
#include <cstdio> #include <vector> #include <queue> using namespace std; struct bead { int rx, ry, bx, by, d; }; int n, m; char a[10][10]; bool check[10][10][10][10]; bead path[10][10][10][10]; queue<bead> q; const char direct[] = {'U', 'R', 'D', 'L'}; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; void move(int &x, int &y, int &c, int dx, int dy) { while (a[x+dx][y+dy] != '#' && a[x][y] != 'O') { x += dx; y += dy; c += 1; } } void bfs() { while (!q.empty()) { int rx = q.front().rx, ry = q.front().ry; int bx = q.front().bx, by = q.front().by; int d = q.front().d; q.pop(); if (d >= 10) break; for (int i=0; i<4; i++) { int nrx = rx, nry = ry, nbx = bx, nby = by; int rc = 0, bc = 0, nd = d+1; move(nrx, nry, rc, dx[i], dy[i]); move(nbx, nby, bc, dx[i], dy[i]); if (a[nbx][nby] == 'O') continue; if (a[nrx][nry] == 'O') { vector<char> p; p.push_back(direct[i]); // Current direct bead &b = path[rx][ry][bx][by]; while (b.rx != 0) { int mrx = b.rx, mry = b.ry, mbx = b.bx, mby = b.by; p.push_back(direct[b.d]); // Go backward previous position. b = path[mrx][mry][mbx][mby]; } printf("%d\n", nd); int len = p.size(); for (int k=0; k<len; k++) { // Print in reverse order. printf("%c", p[len-k-1]); } printf("\n"); return; } if (nrx == nbx && nry == nby) { if (rc > bc) nrx -= dx[i], nry -= dy[i]; else nbx -= dx[i], nby -= dy[i]; } if (check[nrx][nry][nbx][nby]) continue; check[nrx][nry][nbx][nby] = true; q.push({nrx, nry, nbx, nby, nd}); path[nrx][nry][nbx][nby] = {rx, ry, bx, by, i}; } } printf("-1\n"); } int main() { scanf("%d %d", &n, &m); int rx = 0, ry = 0, bx = 0, by = 0; for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { scanf("%1s", &a[i][j]); if (a[i][j] == 'R') rx = i, ry = j; else if (a[i][j] == 'B') bx = i, by = j; } } q.push({rx, ry, bx, by, 0}); check[rx][ry][bx][by] = true; bfs(); return 0; }
Python 3 소스코드
from sys import stdin from collections import deque input = stdin.readline n, m = map(int, input().split()) a = [list(input().strip()) for _ in range(n)] check = [[[[False]*m for _ in range(n)] for _ in range(m)] for _ in range(n)] path = [[[[[0, 0, 0, 0, 0] for _ in range(m)] for _ in range(n)] for _ in range(m)] for _ in range(n)] direct = ('U', 'R', 'D', 'L') dx, dy = (-1, 0, 1, 0), (0, 1, 0, -1) q = deque() def init(): _rx, _ry, _bx, _by = [0]*4 for i in range(n): for j in range(m): if a[i][j] == 'R': _rx, _ry = i, j elif a[i][j] == 'B': _bx, _by = i, j q.append((_rx, _ry, _bx, _by, 0)) check[_rx][_ry][_bx][_by] = True def move(_x, _y, _dx, _dy, _c): while a[_x+_dx][_y+_dy] != '#' and a[_x][_y] != 'O': _x += _dx _y += _dy _c += 1 return _x, _y, _c def bfs(): while q: rx, ry, bx, by, d = q.popleft() if d >= 10: break for i in range(4): nrx, nry, rc = move(rx, ry, dx[i], dy[i], 0) nbx, nby, bc = move(bx, by, dx[i], dy[i], 0) if a[nbx][nby] == 'O': continue if a[nrx][nry] == 'O': p = list() p.append(direct[i]) mrx, mry, mbx, mby = rx, ry, bx, by while mrx: mrx, mry, mbx, mby, k = path[mrx][mry][mbx][mby] p.append(direct[k]) print(d+1) p.pop() p.reverse() print(''.join(p)) return if nrx == nbx and nry == nby: if rc > bc: nrx, nry = nrx-dx[i], nry-dy[i] else: nbx, nby = nbx-dx[i], nby-dy[i] if not check[nrx][nry][nbx][nby]: check[nrx][nry][nbx][nby] = True q.append((nrx, nry, nbx, nby, d+1)) path[nrx][nry][nbx][nby] = (rx, ry, bx, by, i) print(-1) init() bfs()
참고
반응형