[백준] 13460_구슬 탈출 2 (Python)

📕 문제

https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

 

💡 풀이법

: 빨간 구슬을 구멍에서 빼낼 수 있는지 최소한의 동작 횟수를 구해야 하기 때문에 bfs를 이용했다.

 

1. 빨간 구슬과 파란 구슬이 두개 다 움직여야 하기 때문에 두개의 deque를 만든다.

(이때, deque에 들어가는 원소는 (x의 좌표, y의 좌표, 현재까지의 동작 횟수) 이다.)

2. while문을 돌면서 구슬을 각자의 deque에서 하나씩 꺼낸다. 

3. 현재까지의 동작 횟수가 10이라면 -1을 리턴한다.

4. 사방으로 회전 시키면서 가능한 방향이면 deque에 넣는다.

5. 회전 했을 때 벽을 만날때까지 계속해서 이동해야하므로, while문을 만들어서 다음 갈 위치가 #(벽)이면 break하도록 한다.

(파란 구슬이 구멍에 먼저 들어가거나 동시에 들어가면 안되기 때문에 구멍을 만나면 바로 break하고 다음 방향을 탐색하도록 한다.)

6. 여기서 회전시켰을 때 파란 구슬과 빨간 구슬이 떨어지는 거리를 구하는데 그 이유는 만약 빨간구슬과 파란구슬이 동시에 같은 위치로 떨어진다면 한 칸에는 한 구슬만 들어갈 수 있기 때문에 누가 먼저 도착했는지를 판단해줘야 하기 때문이다.

7. 빨간구슬이 떨어지다가 구멍을 만나면 현재까지의 회전 횟수를 리턴한다.

 

from collections import deque
def bfs(B_start, R_start):
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    B_deq = deque([(B_start[0], B_start[1], 0)])
    R_deq = deque([(R_start[0], R_start[1], 0)])

    while B_deq and R_deq:
        B_x, B_y, d = B_deq.popleft()
        R_x, R_y, d = R_deq.popleft()
        if d == 10:
            return -1
        
        flag = False
        for dx, dy in dxy:
            B_cnt = 0
            B_nx, B_ny = B_x, B_y
            while True:
                B_nx, B_ny = B_nx + dx, B_ny + dy
                if (B_nx, B_ny) == hole:
                    flag = True
                    continue
                if board[B_nx][B_ny] == '#':
                    B_nx, B_ny = B_nx - dx, B_ny - dy
                    break
                B_cnt += 1

            if flag:
                flag = False
                continue

            R_cnt = 0
            R_nx, R_ny = R_x, R_y
            while True:
                R_nx, R_ny = R_nx + dx, R_ny + dy
                if (R_nx, R_ny) == hole:
                    return d + 1
                if board[R_nx][R_ny] == '#':
                    R_nx, R_ny = R_nx - dx, R_ny - dy
                    if (R_nx, R_ny) == (B_nx, B_ny):
                        if B_cnt < R_cnt:
                            R_nx, R_ny = R_nx - dx, R_ny - dy
                        else:
                            B_nx, B_ny = B_nx - dx, B_ny - dy
                    if (R_nx, R_ny) != (R_x, R_y) or (B_nx, B_ny) != (B_x, B_y):
                        R_deq.append((R_nx, R_ny, d+1))
                        B_deq.append((B_nx, B_ny, d+1))
                    break
                R_cnt += 1
    return -1

N, M = map(int, input().split())
board = [list(input()) for _ in range(N)]
for i in range(N):
    for j in range(M):
        if board[i][j] == 'B':
            B_start = (i, j)
        elif board[i][j] == 'R':
            R_start = (i, j)
        elif board[i][j] == 'O':
            hole = (i, j)
print(bfs(B_start, R_start))