[백준 15653번] 구슬 탈출 4 (Python3)

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

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))
memory = set()

result = -1
while dq:
  ry,rx,by,bx,direction,cnt = dq.popleft()
  if (ry,rx,by,bx) in memory:
    continue
  memory.add((ry,rx,by,bx))
  if by == 0:
    continue
  if ry == 0:
    result = cnt
    break
  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))

print(result)

 

구슬탈출 1,3처럼 구슬탈출 2 코드로 날먹했다.

구슬탈출 2 코드에서 cnt 제한을 해제하고, 대신 빨간공, 파란공의 현 위치를 memory라는 set를 만들어 그 안에 튜플로 저장한다. 그리고 만약 현 위치가 memory set에 이미 들어있었다면 똑같은 위치로 돌아왔다는 뜻이므로 continue 해준다.

 

구슬탈출 2만 제대로 풀면 구슬탈출 1,3,4를 전부 1초만에 풀 수 있다 ㅋㅋㅋ

 

 

오늘의 교훈) 날먹은 재미있다