[백준 15644번] 구슬 탈출 3 (Python3)

import sys
input = sys.stdin.readline
from collections import deque
dy = [1,0,-1,0]
dx = [0,1,0,-1]
D = "DRUL"

N,M = map(int,input().split())

board = []
for i in range(N):
  board.append(list(input().strip()))

def go(y,x,direction,opcolor):
  while True:
    y1 = y+dy[direction]
    x1 = x+dx[direction]
    if (y1,x1) == opcolor:
      break
    if board[y1][x1] == "O":
      return 0,0
    if board[y1][x1] == ".":
      y,x = y1,x1
    else:
      break
  return y,x

def check(y,x,direction):
  clear = set()
  for i in range(4):
    if (i+direction)%2==0 and direction != -1:
      continue
    y1 = y+dy[i]
    x1 = x+dx[i]
    if board[y1][x1] != "#":
      clear.add(i)
  return clear

for i in range(N):
  for j in range(M):
    if board[i][j] == "R":
      red = [i,j]
      board[i][j] = "."
    if board[i][j] == "B":
      blue = [i,j]
      board[i][j] = "."

dq = deque()
dq.append((red[0],red[1],blue[0],blue[1],-1,0,""))

result = -1
while dq:
  ry,rx,by,bx,direction,cnt,path = dq.popleft()
  if by == 0:
    continue
  if ry == 0:
    result = cnt
    resultpath = path
    break
  if cnt == 10:
    continue
  clearR = check(ry,rx,direction)
  clearB = check(by,bx,direction)
  for direction in clearR|clearB:
    ry1,rx1 = go(ry,rx,direction,(by,bx))
    by1,bx1 = go(by,bx,direction,(ry1,rx1))
    if ry1:
      ry1,rx1 = go(ry1,rx1,direction,(by1,bx1))
    dq.append((ry1,rx1,by1,bx1,direction,cnt+1,path+D[direction]))

print(result)
if result != -1:
  print(resultpath)

구슬탈출 2 코드에서 path만 추가해주고 날먹했다. [백준 13460번] 구슬 탈출 2 (Python3) (tistory.com) 참고

 

구슬탈출 2 코드에서 dq에 넣는 튜플에 path 항목을 추가하고, path에는 경로를 저장해주면 된다. 경로는 4방향 for문을 돌릴 때 저장한다.

 

오늘의 교훈) 구슬 탈출 4도 풀어보자