[파이썬] 백준 알고리즘 No.13460 구슬 탈출 2

나의 코드

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
maps = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for i in range(n):
    maps.append(list(input()))
    for j in range(m):
        if maps[i][j] == 'R':
            rx, ry = i, j
        elif maps[i][j] == 'B':
            bx, by = i, j


def bfs(rx, ry, bx, by):
    count = 0
    queue = deque()
    queue.append((rx, ry, bx, by))
    visited = [(rx, ry, bx, by)]

    while queue:
        for _ in range(len(queue)):
            rx, ry, bx, by = queue.popleft()
            if count > 10:
                return -1

            if maps[rx][ry] == 'O':
                return count

            for i in range(4):
                nrx, nry = rx, ry
                while True:
                    nrx += dx[i]
                    nry += dy[i]
                    if maps[nrx][nry] == '#':
                        nrx -= dx[i]
                        nry -= dy[i]
                        break
                    elif maps[nrx][nry] == 'O':
                        break

                nbx, nby = bx, by
                while True:
                    nbx += dx[i]
                    nby += dy[i]
                    if maps[nbx][nby] == '#':
                        nbx -= dx[i]
                        nby -= dy[i]
                        break
                    elif maps[nbx][nby] == 'O':
                        break

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

                if nrx == nbx and nry == nby:
                    if abs(nrx - rx) + abs(nry - ry) > abs(nbx - bx) + abs(nby - by):
                        nrx -= dx[i]
                        nry -= dy[i]
                    else:
                        nbx -= dx[i]
                        nby -= dy[i]

                if (nrx, nry, nbx, nby) not in visited:
                    queue.append((nrx, nry, nbx, nby))
                    visited.append((nrx, nry, nbx, nby))
        count += 1
    return -1

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

 

풀이 방법

1. 파란 구슬과 빨간 구슬을 각각 움직여야 함

2. 움직이면서 벽이나 구멍을 만나면 아웃

3. 파란 구슬만 구멍에 들어갔거나, 빨간 구슬과 함께 들어갔다면 아웃