[백준 13460번] 구슬 탈출 2 (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))

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

print(result)

아이디어는 크게 어렵지 않았는데 디버깅하는 과정이 살짝 까다로웠던 문제

BFS로 해결하였다.

 

알고리즘을 요약하자면 이러하다.

 

1. 일단 맵에서 R공 B공의 위치를 저장한 뒤 지운다.

2. dq의 튜플에 현재 r공의 위치, b공의 위치, 방금전에 움직인 방향, 지금까지 움직인 횟수를 저장한다.

3. check함수를 실행하여 방금 온 방향에서 좌, 우 방향에 벽이 있는지를 확인하고 없다면 저장한다.

4. check함수에서 저장한 방향만큼 for문을 돌리고 go함수를 실행한다

5. 이때 어느공이 앞에있는지 모르니, 처음에 이동한 공을 한번 더 이동한다. (중요 포인트!)

6. O를 만나면 결과값을 출력한다.

 

처음에는 R공만 벽이 있는지만 체크하면 된다고 생각하였다. 그런데 R공이 막혀있어도 B공도 고려해야한다는 사실을 깨달았다.

 

참고로 구슬탈출 1은 2와 똑같은데 횟수가 아닌 가능성을 출력하는 문제이다. 따라서 구슬탈출 2만 풀면 날먹이 가능하다 ㅋㅋ

 

 

오늘의 교훈) 다양한 요소를 고려하자