[백준 6087번] 레이저 통신 (Python3)

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

def BFS():
  global dq
  visited = [[0]*M for i in range(N)]
  visitedd = [[{} for i in range(M)] for i in range(N)]
  result = 10**6

  while dq:
    y,x,cnt,d = dq.popleft()
    if visited[y][x] and visited[y][x] < cnt:
      continue
    if visited[y][x] == cnt:
      if d in visitedd[y][x]:
        continue
      else:
        visitedd[y][x].add(d)
    else:
      visited[y][x] = cnt
      visitedd[y][x] = {d}
    if board[y][x] == "C":
      result = min(result,cnt-1)
      continue
    for i in range(4):
      if (d-i)%4 == 2:
        continue
      y1,x1 = y+dy[i],x+dx[i]
      if N>y1>=0 and M>x1>=0:
        if board[y1][x1] == "*":
          continue
        dq.append((y1,x1,cnt+((d+i)%2),i))
  print(result) 

def findC():
  global C,dq
  for y in range(N):
    for x in range(M):
      if board[y][x] == "C":        
        for i in range(4):
          y1,x1 = y+dy[i],x+dx[i]
          if N>y1>=0 and M>x1>=0:
            if board[y1][x1] != "*":
              dq.append((y1,x1,1,i))
        return
          
M,N = map(int,input().split())

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

dq = deque()
findC()
BFS()

 

전형적인 BFS 문제인데 실수할 여지가 있는 문제였다.

 

일단 알고리즘을 요약하면

1. C의 좌표를 찾은 뒤, C를 기준으로 4방향에 대해 열려있으면 해당 방향으로 한칸 나간 좌표+방향을 dq에 넣는다.

2. visited를 1로 기록하는 것이 아닌 지금까지 방향전환한 개수 cnt를 입력한다. (이때 cnt는 1부터 시작)

3. 현 위치의 visited가 현재의 방향전환 개수보다 적으면 continue

4. 4방향 BFS를 할때 방향이 바뀌면 cnt를 +1 해준다.

5. C에 도착하더라도 BFS를 멈춰선 안된다

6. 가장 작은값 출력

 

내가 실수한 부분은 3번이었다. 현 위치의 visited가 방향전환 개수보다 적으면 continue를 해주어야 하는데 적거나 같으면 continue를 해주었다. 이렇게 되자 같은 cnt더라도 방향이 다른 경우에 대해서 최솟값이 달라질 수 있었다.

 

 

오늘의 교훈) 빠질 수 있는 경우의 수를 유의하자