# 거울 설치 - BOJ

# 문제

채영이는 거울을 들여다보는 것을 참 좋아한다. 그래서 집 곳곳에 거울을 설치해두고 집 안을 돌아다닐 때마다 거울을 보곤 한다.

채영이는 새 해를 맞이하여 이사를 하게 되었는데, 거울을 좋아하는 그녀의 성격 때문에 새 집에도 거울을 매달만한 위치가 여러 곳 있다. 또한 채영이네 새 집에는 문이 두 개 있는데, 채영이는 거울을 잘 설치하여 장난을 치고 싶어졌다. 즉, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 거울을 설치하고 싶어졌다.

채영이네 집에 대한 정보가 주어졌을 때, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 하기 위해 설치해야 하는 거울의 최소 개수를 구하는 프로그램을 작성하시오.

거울을 설치할 때에는 45도 기울어진 대각선 방향으로 설치해야 한다. 또한 모든 거울은 양면 거울이기 때문에 양 쪽 모두에서 반사가 일어날 수 있다. 채영이는 거울을 매우 많이 가지고 있어서 거울이 부족한 경우는 없다고 하자.

거울을 어떻게 설치해도 한 쪽 문에서 다른 쪽 문을 볼 수 없는 경우는 주어지지 않는다.

[입력]

첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다.

[출력]

첫째 줄에 설치해야 할 거울의 최소 개수를 출력한다.

# 풀이

BFS로 접근
거울이 45도 각도로 있다고 했으므로 거울에 대각선 방향으로 들어온다면 입사각 그대로 반사되어 나갈 것이므로 제외. 동서남북 4방향으로만 탐색하면 된다.
'#'(문) 의 위치에서부터 시작해서 벽이 아닌 곳을 큐에 집어넣고 탐색. 이때 큐에 들어가는 것은 다음 좌표와 거울의 개수, 방향 이다.
방문하지 않았거나, 전에 탐색했을 때보다 거울의 개수가 작다면, 거울의 개수를 갱신하며 탐색
거울에 상하로 들어왔다면 좌우 방향으로 나갈 수 있을 것이고, 좌우로 들어왔다면 상하 방향으로 나갈 수 있을 것이다.
거울 설치가 최소로 되는 것을 찾으라고 했으므로 거울을 만났을 때 부딪히지 않고 지나치는 경우를 추가해 주어야 한다. 이 부분을 생각하지 못하여 WA가 떴었다.

from collections import deque

dy = [-1,1,0,0]
dx = [0,0,-1,1]

N = int(input())
house = [list(input()) for _ in range(N)]
door, mirror = [], []
ret = float('inf')

for i in range(N):
    for j in range(N):
        if house[i][j] == '#':
            door.append([i, j])

y, x = door[0]
desy, desx = door[1]
visit = {}
q = deque()

for way in range(4):
    nx = x + dx[way]
    ny = y + dy[way]
    if 0 > nx or 0 > ny or ny >= N or nx >= N:
        continue
    if house[ny][nx] != '*':
        q.append((nx, ny, 0, way)) # 좌표, cnt, 방향

while q:
    x, y, cnt, way = q.popleft()
    if 0 > x or 0 > y or y >= N or x >= N:
        continue
    if visit.get((x, y, way)) == None or visit[(x, y, way)] > cnt: # 방문하지 않았거나, 탐색했던 것보다 거울 개수가 작다면 갱신
        visit[(x, y, way)] = cnt
        nx = x + dx[way]
        ny = y + dy[way]
        if x == desx and y == desy:
            ret = min(cnt, ret)
        elif house[y][x] == '.':
            q.append((nx, ny, cnt, way))
        elif house[y][x] == '!':
            q.append((nx, ny, cnt, way)) # 거울이 해당 자리에 있더라도 지나치는 경우
            if way == 0 or way == 1:
                q.append((x + dx[2], y + dy[2], cnt + 1, 2))
                q.append((x + dx[3], y + dy[3], cnt + 1, 3))
            else:
                q.append((x + dx[0], y + dy[0], cnt + 1, 0))
                q.append((x + dx[1], y + dy[1], cnt + 1, 1))
print(ret)