[백준/python/13459] 구슬탈출

문제링크 : 구슬탈출

달이 차오른다 문제와 비슷하지만 조건이 더 까다로운 문제다.

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

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

def bfs(rx,ry,bx,by):
    q=deque()
    q.append((rx,ry,bx,by))
    visited=[]
    visited.append((rx,ry,bx,by))
    count=0
    while q:
        for _ in range(len(q)):
            rx,ry,bx,by=q.popleft()
            if count>10:
                print(0)
                return
            if board[rx][ry]=='O':
                print(1)
                return
            for i in range(4):
                now_rx,now_ry=rx,ry
                while True:
                    now_rx+=dx[i]
                    now_ry+=dy[i]
                    if board[now_rx][now_ry]=='#':
                        now_rx-=dx[i]
                        now_ry-=dy[i]
                        break
                    if board[now_rx][now_ry]=='O':
                        break
                now_bx,now_by=bx,by
                while True:
                    now_bx += dx[i]
                    now_by += dy[i]
                    if board[now_bx][now_by] == '#':
                        now_bx -= dx[i]
                        now_by -= dy[i]
                        break
                    if board[now_bx][now_by] == 'O':
                        break
                if board[now_bx][now_by]=='O':
                    continue
                if now_rx==now_bx and now_ry==now_by:
                    if abs(now_rx-rx)+abs(now_ry-ry)>abs(now_bx-bx)+abs(now_by-by):
                        now_rx-=dx[i]
                        now_ry-=dy[i]
                    else:
                        now_bx-=dx[i]
                        now_by-=dy[i]
                if (now_rx,now_ry,now_bx,now_by) not in visited:
                    q.append((now_rx,now_ry,now_bx,now_by))
                    visited.append((now_rx,now_ry,now_bx,now_by))
        count+=1
    print(0)


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

bfs(rx,ry,bx,by)

구현하는게 복잡한 문제이다. 파란공이 먼저 구멍에 들어가는 경우, 파란공과 빨간공이 겹치는 경우 등을 따져줘야한다. 처음에 왜 방문했던 경로를 visited 배열로 쌓을까 생각했었는데 한칸씩 움직이는게 아니라 벽을 만날때까지 움직이는 것이기 때문에 visited배열이 많이 커지지 않았던것 같다.