[Python] 백준 13460번: 구슬 탈출 2

최소 depth를 구하는 문제이므로, 빨간 구슬만 구멍을 탈출했다면 바로 depth를 출력한 후 종료할 수 있는 bfs를 사용하여 탐색합니다.

bfs이므로 방문 체크를 해야 하는데요, 이와 같이 구슬이 움직이는 문제에서는 각 구슬의 위치들인 (빨간구슬 X, 빨간구슬 Y, 파란구슬 X, 파란구슬 Y)가 node이므로, (빨간구슬 X, 빨간구슬 Y, 파란구슬 X, 파란구슬 Y)를 visited 배열에 추가하여 방문 체크를 합니다.

로직

1. cnt > 10 이면 break
2. 상하좌우에 대해
   a. 빨간 구슬과 파란구슬 움직이기
   b. 파란구슬이 구멍으로 빠졌다면? → stop (=continue 하여 그 다음 q 확인)
   c. 빨간구슬만 구멍으로 빠졌다면? → cnt 출력
   d. 둘다 구멍으로 안빠졌고, 위치가 겹쳤다면? → 더 최근에 이동한 구슬을 한칸 전으로 이동
   e. (빨간구슬 X, 빨간구슬 Y, 파란구슬 X, 파란구슬 Y)에 방문한 적 없다면? → q에 추가하고 visited에 추가

코드

from collections import deque
n, m = map(int, input().split())
board = [list(input()) for _ in range(n)]

rx, ry, bx, by = 0, 0, 0, 0

for i in range(n):
    for j in range(m):
        if board[i][j] == 'R':
            rx, ry = i, j
        elif board[i][j] == 'B':
            bx, by = i, j

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def move(x, y, d):
    cnt = 0
    while board[x][y] != 'O' and board[x+dx[d]][y+dy[d]] != '#':
        x += dx[d]
        y += dy[d]
        cnt += 1
    return x, y, cnt


def bfs(rx, ry, bx, by):
    q = deque([(rx, ry, bx, by, 1)])
    visited = [(rx, ry, bx, by)]    # 파란 구슬의 위치도 방문 체크에 포함해야함
    while q:
        rx, ry, bx, by, cnt = q.popleft()

        if cnt > 10:
            break

        for i in range(4):
            nrx, nry, rCnt = move(rx, ry, i)
            nbx, nby, bCnt = move(bx, by, i)

            if board[nbx][nby] == 'O':
                continue

            if board[nrx][nry] == 'O':
                return cnt

            if (nrx, nry) == (nbx, nby):
                if rCnt > bCnt:
                    nrx -= dx[i]
                    nry -= dy[i]
                else:
                    nbx -= dx[i]
                    nby -= dy[i]

            if (nrx, nry, nbx, nby) not in visited:
                visited.append((nrx, nry, nbx, nby))
                q.append((nrx, nry, nbx, nby, cnt + 1))
    return -1


print(bfs(rx, ry, bx, by))