반응형
알고리즘 분류 : BFS
보드 위에 빨간 구슬과 파란 구슬이 있고, 빨간 구슬만 구멍으로 빠뜨리는 문제다. 구슬 탈출 문제 시리즈는 이 문제를 포함하여, 총 4문제이다.
파란 구슬이 구멍에 빠져서는 안되고, 파란 구슬과 빨간 구슬이 동시에 빠져서도 안 된다. 또한 빨간 구슬과 파란 구슬이 동시에 움직이고, 굴리면 벽에 부딪힐 때까지 굴러간다. 구슬 2개가 동시에 움직이기 때문에 4차원 배열을 통해 방문 여부를 체크해주면 편하다.
- Queue에 빨간 구슬의 (X, Y) 좌표, 파란 구슬의 (X, Y) 좌표를 모두 넣는다.
- 방문 여부를 확인할 check 배열을 4차원 배열로 선언한다. 배열의 인덱스는 [빨간 X좌표] [빨간 Y좌표] [파란 X좌표] [파란 Y좌표] 이다.
- 구슬을 굴릴 때, 구슬의 다음 위치가 벽(#)인지, 구슬의 현재 위치가 구멍(O)인지 확인한다.
- 구슬의 다음 위치가 벽이라면 앞으로 가지 못한다. 구슬의 현재 위치가 구멍이라면, 현재 구슬의 색이 무엇인지 판별한다.
- 만약 파란 구슬의 현재 위치가 구멍이라면 무시하고, 빨간 구슬의 현재 위치가 구멍이라면, 1을 출력하고 종료한다.
- 구슬을 굴리면서, 빨간 구슬의 이동 거리와 파란 구슬의 이동 거리를 카운트해야 한다.
- 구슬을 굴린 후, 빨간 구슬의 위치와 파란 구슬의 위치가 같다면, 이동 거리 비교를 통해 겹치지 않도록 처리해야 한다.
- 만약 구슬이 겹쳤다면, 굴릴 때 카운트했던 이동 거리가 더 긴 구슬의 위치를 한 칸 이전으로 되돌린다.
- 굴리는 과정이 10번을 넘어가면 그대로 종료하고, 0을 출력한다.
- 더 이상 갈 곳이 없을 때에는 BFS를 빠져나와서 0을 출력한다.
C++ 소스코드
#include <cstdio> #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]; queue<bead> q; 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; move(nrx, nry, rc, dx[i], dy[i]); // Moving red bead. move(nbx, nby, bc, dx[i], dy[i]); // Moving blue bead. if (a[nbx][nby] == 'O') continue; // Blue bead cannot fall into hole. if (a[nrx][nry] == 'O') { // Red bead falls into hole. printf("1\n"); return; } if (nrx == nbx && nry == nby) { // Beads cannot be placed in the same position. if (rc > bc) nrx -= dx[i], nry -= dy[i]; // Go back to previous. else nbx -= dx[i], nby -= dy[i]; } if (check[nrx][nry][nbx][nby]) continue; // Already visited. check[nrx][nry][nbx][nby] = true; q.push({nrx, nry, nbx, nby, d+1}); } } printf("0\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)] 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': print(1) 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)) print(0) init() bfs()
참고
반응형