백준 13460번 : 구슬 탈출 2 in Python
이 문제는 직사각형 보드에서 구멍을 통해 빨간 구슬을 빼낼 때 보드를 기울이는 횟수의 최솟값을 구하는 문제이다. 단, 파란 구슬이 구멍으로 빠지면 안 된다.
우선 이 문제는 그래프 탐색 문제로 볼 수 있고, 특히 구슬들의 이동 횟수의 최솟값을 묻고 있기 때문에 너비 우선 탐색을 적용해야 한다. 단, 이동할 때 한 칸씩 움직이는 게 아니라 벽이나 구멍, 다른 구슬을 만날 때까지 움직이기 때문에 이를 구현할 때 주의해야 한다.
보드를 한쪽 방향으로 기울였을 때 구슬이 움직이는 것을 구현하는 함수를 만들어보자. 우선 매개변수로 그 구슬의 현재 좌표와 이동 방향이 주어져야 할 것이다. 그리고 구슬은 벽이나 구멍을 만날 때까지 움직이므로 while의 조건문에서 이동한 뒤의 좌표가 구멍이거나 아니면 한 번 더 이동했을 때의 좌표가 벽이 될 때까지, 즉 벽에 부딪칠 때까지 구슬을 이동 방향으로 움직인다. 이때, 여기서 구슬과 만날 경우를 고려하지 않았는데, 이는 나중에 구현하도록 하겠다.
이제 이 함수를 가지고 BFS를 구현해 보자. 우선 초기값부터 설정한다. 맨 처음 빨간 구슬과 파란 구슬의 좌표를 알아내 (현재까지의 이동 횟수+1)을 나타내는 변수를 포함해 queue에 넣는다. 그리고 보드 내 각 좌표를 이미 방문했는지를 나타내는 N*M*N*M 크기의 check 행렬을 만든다. 여기서 check[rx][ry][bx][by]는 빨간 구슬의 좌표가 (rx, ry), 파란 구슬의 좌표가 (bx, by)인 경우를 조사했었는지를 나타낸다.
이제 본격적으로 BFS를 구현한다. 일단 queue에서 원소를 꺼냈을 때 이동 횟수가 10이 넘어가는지를 확인한다. 그리고 동서남북 네 방향으로 보드를 기울인 경우를 생각해 새로운 빨간 구슬의 좌표, 파란 구슬의 좌표를 구한다. 이때 파란 구슬은 어떠한 경우에도 구멍에 들어가선 안 되기 때문에, 일단 이동 결과 파란 구슬의 위치가 구멍인지를 확인한다. 물론 빨간 구슬과 파란 구슬의 위치가 겹치는 경우가 있을 수 있다. 하지만, 이러한 경우 파란 구슬이 먼저 구멍에 도달한 것일 수도 있고, 빨간 구슬이 먼저 구멍에 도달했을 수도 있다. 두 경우 모두 결국 파란 구슬이 구멍에 도달하게 돼 결국 빠지게 된다. 따라서 구슬의 위치가 겹치더라도 이동 후 파란 구슬의 위치가 구멍이 돼서는 안 된다.
이를 확인한 뒤, 빨간 구슬이 구멍에 도달한 경우, 아직까지 출력한 결과가 없으면 (이동 횟수+1)을 출력한다. 다만 queue에 저장할 때 이동 횟수에 이미 1을 더한 상태로 저장했으므로 이를 그대로 출력하면 된다. 그 다음, 이제 빨간 구슬과 파란 구슬의 위치가 겹치는 경우를 생각해야 한다. 이는 두 구슬이 같은 x축(y축)에 있는 상황에서 x축 방향(y축 방향)으로 이동한 경우에 해당할 것이다. 그러면 더 적게 이동한 구슬이 먼저 벽이나 구멍에 도달했을 것이고, 따라서 나중에 도달한 구슬의 위치를 이동 방향과 반대 방향으로 한 칸 옮겨야 한다. 이를 고려하기 위해 이전에 정의했던 구슬의 이동을 구현한 함수에 이동한 칸 수를 나타내는 변수 c를 추가한다. 그리고 while loop을 돌 때 c의 값을 1씩 증가시켜 c도 결과값으로 반환한다. 그러면 이 결과를 통해 어떤 구슬이 먼저 도착했는지 알 수 있을 것이다.
마지막으로 두 구슬이 이동한 뒤 좌표에 대응하는 check의 entry를 구해 아직 방문하지 않은 좌표면 queue에 해당 좌표와 (이동 횟수+1)을 포함한 배열을 넣는다. while loop을 벗어난 뒤에도 출력한 결과가 없으면 빨간 구슬이 이동 횟수 10 이하로 구멍에 도달하지 못하는 경우이므로 -1을 출력한다.
이를 코드로 구현하면 다음과 같다.
from collections import deque
N, M = map(int, input().split())
board = []
for _ in range(N):
board.append(input().strip())
# 초기 구슬의 좌표
red = [0, 0]
blue = [0, 0]
for i in range(N):
for j in range(M):
if board[i][j] == 'R':
red[0] = i; red[1] = j
if board[i][j] == 'B':
blue[0] = i; blue[1] = j
queue = deque()
queue.append([1, red, blue])
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# 두 구슬이 보드 내 좌표를 방문했었는지를 나타내는 행렬
check = [[[[False]*M for _ in range(N)] for _ in range(M)] for _ in range(N)]
check[red[0]][red[1]][blue[0]][blue[1]] = True
printed = False
# 구슬의 이동을 구현하는 함수
def move(_x, _y, _dx, _dy):
# 구슬의 위치가 겹치는 경우 어떤 구슬이 더 앞에 있었는지를 알기 위해
# 구슬의 이동 거리를 나타내는 변수를 추가한다.
_c = 0
# 벽에 부딪치거나 구멍에 도달할 때까지 이동한다.
while board[_x+_dx][_y+_dy] != '#' and board[_x][_y] != 'O':
_x += _dx
_y += _dy
_c += 1
return _x, _y, _c
while len(queue) > 0:
d, R, B = queue.popleft()
if d > 10: break
for i in range(4):
nRx, nRy, Rc = move(R[0], R[1], dx[i], dy[i])
nBx, nBy, Bc = move(B[0], B[1], dx[i], dy[i])
# 파란 구슬이 구멍에 도달하지 않는 경우에만 실행한다.
if board[nBx][nBy] != 'O':
if board[nRx][nRy] == 'O' and not printed:
print(d)
printed = True
break
# 두 구슬의 위치가 겹치는 경우 이동 거리를 비교해 뒤에 있어야 할 구슬을 뒤로 한 칸 보낸다.
if nRx == nBx and nRy == nBy:
if Rc > Bc : nRx -= dx[i]; nRy -= dy[i]
else: nBx -= dx[i]; nBy -= dy[i]
if not check[nRx][nRy][nBx][nBy]:
check[nRx][nRy][nBx][nBy] = True
queue.append([d+1, [nRx, nRy], [nBx, nBy]])
if not printed: print(-1)