백준 2151 거울 설치

https://www.acmicpc.net/problem/2151

문제를 읽고 처음에는 잘 이해가 안됬지만, 결국에 결론은 다음과 같다.

• 거울은 양면이므로, 북에서 들어온 빛은 동쪽 혹은 서쪽으로 꺾인다 동쪽에서 온 빛은 남쪽 혹은 북쪽으로 꺾인다.

결국 한쪽 문에서 bfs를 시작해 다른 쪽 문이 나올때까지 찾으면 되는데,
문제는 거울을 어떻게 설치할 것인가이다.
거울의 위치를 다 기록해놔 거울의 3가지 상태를 가진 테이블을 모두 조합해 브루트 포스로 풀어도 된다.
하지만, 반복을 제거하기 위해, 방문배열을 만들었고, 특정 위치에서 특정 방향으로 가는 빛의 상태를 저장한 적이 있다면, 그 경로에 설치한 거울의 수가 현재 거울의 수보다 작아야만 더 탐색할 수 있도록 만들었다.

from collections import deque
n = int(input())
arr = []
door = []
mirror = []
dx = [-1,0,1,0]
dy = [0,1,0,-1]
ans = 5000
visited = [[[5000]*4 for i in range(n)] for i in range(n)]
for i in range(n):
    row = list(input())
    for j in range(n):
        if row[j] == '#':
            door.append((i,j))
        if row[j] == '!':
            mirror.append((i,j))
    arr.append(row)
queue = deque([])
x,y = door[0][0], door[0][1]
for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0 <= nx < n and 0 <= ny < n and arr[nx][ny] != '*':
        queue.append((x,y,i,0))
while queue:
    x,y,d,cnt = queue.popleft()
    if visited[x][y][d] <= cnt:
        continue
    visited[x][y][d] = cnt
    if x == door[1][0] and y == door[1][1]:
        ans = min(ans,cnt)
    nx = x + dx[d]
    ny = y + dy[d]
    if 0 <= nx < n and 0 <= ny < n and arr[nx][ny] != '*':
        if arr[nx][ny] == '!': ## 거울 설치할지 안할지
            if d == 0 or d == 2:
                for nd in [1,3]:
                    queue.append((nx,ny,nd,cnt+1))
            if d == 1 or d == 3:
                for nd in [0,2]:
                    queue.append((nx,ny,nd,cnt+1))
        queue.append((nx,ny,d,cnt)) ## 거울 설치 안할때
print(ans)