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더라도 방향이 다른 경우에 대해서 최솟값이 달라질 수 있었다.
오늘의 교훈) 빠질 수 있는 경우의 수를 유의하자