[Python/파이썬] 백준 15644번 구슬 탈출 3

15644번: 구슬 탈출 3

 

코드

from collections import deque

n, m = map(int, input().split())
board = []
rx, ry = 0, 0
bx, by = 0, 0
for i in range(n):
    row = list(input().rstrip())
    for j in range(m):
        if row[j] == 'R':
            rx, ry = i, j
        elif row[j] == 'B':
            bx, by = i, j
    board.append(row)

# BFS
q = deque([(rx, ry, bx, by, '')])
visited = set()
visited.add((rx, ry, bx, by))
board[rx][ry] = '.'
board[bx][by] = '.'
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
dd = ['L', 'R', 'U', 'D']


def marble_move(x, y, d):   # 구슬 이동
    while True:
        x += dx[d]
        y += dy[d]
        if board[x][y] == 'O':
            return [x, y]
        if board[x][y] == '#':
            x -= dx[d]
            y -= dy[d]
            return [x, y]


while q:
    rx, ry, bx, by, mv = q.popleft()
    if len(mv) >= 10:
        break
    for i in range(4):
        nrx, nry = marble_move(rx, ry, i)   # 빨간 구슬 이동
        nbx, nby = marble_move(bx, by, i)   # 파란 구슬 이동
        if board[nbx][nby] == 'O':  # 파란 구슬이 구멍에 빠지는 경우
            continue
        if board[nrx][nry] == 'O':  # 빨간 구슬이 구멍에 빠지는 경우
            print(len(mv)+1)
            print(mv+dd[i])
            exit()
        if nrx == nbx and nry == nby:   # 빨간 구슬과 파란 구슬이 겹치는 상황
            if abs(nrx-rx)+abs(nry-ry) < abs(nbx-bx)+abs(nby-by):
                nbx -= dx[i]
                nby -= dy[i]
            else:
                nrx -= dx[i]
                nry -= dy[i]
        if (nrx, nry, nbx, nby) not in visited:
            q.append((nrx, nry, nbx, nby, mv+dd[i]))
            visited.add((nrx, nry, nbx, nby))

print(-1)

 

BFS로 풀 수 있는 문제이지만 다른 문제들과 다른 점들이 있다.

 

1. 한 번 기울이면 한 칸만 이동하는 것이 아니라 벽이나 다른 구슬에 막히거나 구멍에 빠지지 않는 이상 계속 간다는 점이다.

2. 파란 구슬은 어떤 경우에도 구멍에 빠지도록 해서는 안되므로 구멍에 빠지는 이동은 continue로 넘어간다.

3. 빨간 구슬과 파란 구슬이 겹칠 수도 없다. 빨간 구슬과 파란 구슬이 겹치는 경우 더 많은 거리를 이동한 구슬이 더 뒤에서 온 구슬이므로 한 칸 뒤로 옮겨주도록 한다.

 

이러한 점들을 변형하여 BFS 알고리즘으로 풀이한다면 풀 수 있다.