[SWEA] 구슬탈출 2

문제조건

• 빨간구슬, 파란구슬 두 개가 동시에 위치 이동을 한다. (정점의 위치가 변한다!)
• 빨간구슬, 파란구슬은 같은 위치에 있을 수 없다. (장애물정점의 위치도 변한다!)
• 한 번 이동 시, 갈 수 있을 때까지 쭈욱 간다.

핵심개념

• BFS에서 queue에는 x,y 좌표 한 개만 담으라는 법은 없다. 빨간구슬의 (x,y), 파란구슬의 (x,y)를 같이 담는다.
• 종료조건을 먼저 생각하자.

1) 움직인 횟수 10번 넘었거나 (실패)
2) 10번 안 넘었지만 탈출할 수 없거나 (실패)
3) 빨간구슬이 탈출에 성공했거나

코드

from collections import deque

n, m = map(int, input().split())
a = [list(map(str, input())) for _ in range(n)]

dist = {}
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]

# 처음 구슬의 위치
q = deque()
for i in range(n):
    for j in range(m):
        if a[i][j] == 'R':
            ri, rj = i, j
        elif a[i][j] == 'B':
            bi, bj = i, j
q.append((ri, rj, bi, bj))
dist[(ri, rj, bi, bj)] = 0


def move(_x, _y, _dx, _dy, _c):
	# _c의 용도는 이동했는데 빨간구슬, 파란구슬이 같은 곳에 있을 때 
    # _c가 많은 구슬을 전 지점으로 보내기 위해서이다.
    # _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 = q.popleft()

        if dist[(rx, ry, bx, by)] >= 10:
            break

        for k in range(4):
            # 이 방향으로 갈 수 있을 때까지 쭈욱 간다.
            nrx, nry, rc = move(rx, ry, dx[k], dy[k], 0)
            nbx, nby, bc = move(bx, by, dx[k], dy[k], 0)

            # 파란구슬이 이동하려는 곳에 구멍이 있는 경우, 다른 방향으로 이동한다.
            if a[nbx][nby] == 'O':
                continue
            # 빨간구슬이 이동하려는 곳에 구멍이 있는 경우,(탈출 성공!)
            if a[nrx][nry] == 'O':
                print(dist[(rx, ry, bx, by)] + 1)
                return

            # 빨간구슬, 파란구슬이 이동한 위치가 같을 때는 (같이 못 있음)
            if nrx == nbx and nry == nby:
                # 빨간구슬이 파란구슬보다 이전에 있어야 하거나
                if rc > bc:
                    nrx, nry = nrx - dx[k], nry - dy[k]
                # 파란구슬이 빨간구슬보다 이전에 있어야 하거나    
                else:
                    nbx, nby = nbx - dx[k], nby - dy[k]

            if not (nrx, nry, nbx, nby) in dist.keys():
                q.append((nrx, nry, nbx, nby))
                dist[(nrx, nry, nbx, nby)] = dist[(rx, ry, bx, by)] + 1

    print(-1)

bfs()