문제링크 : 구슬탈출
달이 차오른다 문제와 비슷하지만 조건이 더 까다로운 문제다.
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배열이 많이 커지지 않았던것 같다.
