[Python 3] BOJ - 2151 "거울 설치"

 # 문제 링크

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

2151번: 거울 설치

 

 # 풀이

 개인적으로 이 문제의 핵심은 BFS라고 생각한다. 문제를 많이 풀었다면 0-1 BFS 혹은 우선순위 큐를 이용한 BFS가 떠오를 것이다. 어느쪽으로 풀어도 정답을 도출할 수 있으나 이번 포스팅은 0-1 BFS로 풀어보겠다. 0-1 BFS에 대해 간략히 설명하자면, 일반적인 BFS에서는 간선의 모든 가중치가 1인데 반해 가중치가 0 혹은 1로만 이루어진 그래프의 최단거리를 찾는 BFS이다. 알고리즘은 매우 간단하다. 0인 간선은 큐의 앞에 추가하고, 1인 간선은 큐의 뒤에 추가해주면 최단거리를 구할 수 있다.

 BFS의 상태공간은 일반적인 2차원이 아닌 방향까지 고려한 3차원이 되어야 한다. 따라서 상태공간을 현재 위치가 (x, y)이고 들어올 때 방향이 dir일 때 설치한 거울의 최소 갯수라고 놓을 수 있다. 또한 주의할 점은 현재 방향대로 계속 이동해야 한다는 점이다. 왜냐하면 시선, 즉 빛은 직선이기 때문이다.

<그림 1. 예제 1에서의 상태 공간>

 위 그림 1은 예제 1에서의 상태공간을 나타낸 것이다. 현재 문에서 북쪽으로 향할 때 거울을 놓을 수 있는 위치에 도달함을 알 수 있다. 그러나, 거울을 놓을 수 있는 위치임에도 불구하고 거울을 놓지 않을 수 있다. 즉, 0-1 BFS에서 간선이 0인 부분과 1인 부분이 둘 다 가능한 상태이다. 이 때 0의 가중치를 가진 간선부터 먼저 큐에 넣어줌으로서 그 다음 큐에서 나오는 경로는 여전히 북쪽을 향할 것이다. 

 그런데 끝까지 북쪽으로 가게 되면 벽에 부딪히게 되고 탐색이 종료된다. 이제 남은 것은 거울을 놓을 수 있는 위치에 거울을 설치하는 상태 공간이다. 북쪽에서 출발한 시선이 거울에 반사가 된다면 가능한 가지는 두 가지 경우인데, 동쪽으로 반사되거나 서쪽으로 반사되는 것이다. 그런데 현재 3행 2열에 놓인 거울이 서쪽으로 반사된다면 바로 벽에 부딪히므로 현재 상태 공간에는 동쪽만 표시된다. 상태 공간의 정의에 따라 (3, 2, East)에 1을 증가시킨다.

<그림 2. 예제 1의 상태 공간>

 그림 2는 그림 1을 이어서 나타낸 상태 공간이다. 한 번 거울에 반사된 빛의 방향은 동쪽이고 다시 거울을 놓을 수 있는 위치에 도달했다. 위에서 했던 것과 같은 논리로 우선은 설치하지 않는 경우를 먼저 탐색한다. 그런데 계속 동쪽으로 가다보면 결국 벽에 부딪히게 된다. 따라서 설치하지 않는 경우의 탐색은 종료된다. 이후 설치하는 경우 탐색을 하게 되면 3행 4열에서 동쪽으로 들어온 빛은 북쪽 아니면 남쪽으로 반사될 것이다. 따라서 해당하는 상태 공간에 1을 증가시킨다.

<그림 3. 예제 1에서의 상태 공간>

 이제 남은 것은 3행 4열에서 거울을 설치한 후, 남쪽과 북쪽으로 전진하는 것이다. 그런데 이 때 어느 쪽을 먼저해도 상관이 없기 때문에 북쪽부터 먼저 간다고 하자. 북쪽으로 계속 이동하다보면 다른 문이 나오게 되고 탐색을 종료한다. 이 때 문은 거울을 설치 할 수 있는 공간이 아니므로 이전 상태 공간(2, 4, North)의 값을 그대로 승계한다.

<그림 4. 예제 1에서의 상태 공간>

 그림 4는 최종적인 상태 공간을 나타낸다. 이전에 처리하지 않았던 남쪽으로 탐색은 계속 하다보면 벽에 막히게 되므로 자연스럽게 탐색을 종료하고 모든 경우를 다 조사했기 때문에 큐는 비게 되고 0-1 BFS는 끝나게 된다. 따라서, 이 때 문이 있는 위치인 (1, 4)에서 4방향을 보게 되면, 북쪽을 제외한 모든 방향은 그 방향으로 1행 4열에 들어갈 수 없지만 북쪽은 거울을 2개를 설치하여 갈 수 있기 때문에 정답이 됨을 알 수 있다.

 그런데 문제에서 집이 항상 벽으로 둘러쌓여있다는 보장이 있는가? 없다. 따라서, 처음 시작하는 문에서 각 4방향을 모두 탐색해야 한다. 예제 1의 경우는 운좋게 북쪽만 탐색해도 정답이 나오기 때문에 주의해야 한다.

<그림 5. n = 3인 경우>

 그림 5에서는 시작방향에서 동쪽으로도 갈 수 있고, 남쪽으로도 갈 수 있다. 위 그림에서는 남쪽으로 이동할 때의 상태공간을 나타낸다. 이 때 1행 3열에서 동쪽 방향으로 들어올 때 설치해야 하는 최소 거울 수는 3이다.

<그림 6. n = 3인 경우>

 그림 6에서는 시작하는 문에서 동쪽으로 이동하는 경우이다. 이 때 1행 3열에서 동쪽으로 들어올 때 설치해야 하는 최소 거울 수는 0이다. 왜냐하면 1행 2열에서 거울을 설치하지 않으면 되기 때문이다. 그런데, 이전에 남쪽에서 시작하는 경우에 의해 이미 상태공간이 채워져버렸다. 왜냐하면 시작하는 문에서 볼 수 있는 방향이 1가지 이상이 되었기 때문이다. 그런데 0-1 BFS에서는 더 작은 가중치를 앞에 추가함으로서 최단 거리를 구한다고 했는데 모순이라고 생각할 수 있다. 결론적으로 0-1 BFS는 틀리지 않았다. 단, 시작하는 문에서 보는 최초 방향에 대한 최단거리이다. 따라서, 다른 방향에 대한 최소 거울 갯수를 바르게 판단하기 위해서는 이전에 구한 최소 거울 갯수보다 더 작다면 상태 공간을 갱신 한 후, 0-1 BFS의 논리에 따라 큐에 추가해야 시작하는 시점이 바뀌어도 전체적인 최소 거울 갯수를 구할 수 있다.

 

# 코드

import sys, collections

# 입력부
n = int(sys.stdin.readline())
arr = [list(sys.stdin.readline().rstrip()) for _ in range(n)]

# dx, dy : 방향배열(북, 남, 동, 서)
dx = [-1,1,0,0]
dy = [0,0,1,-1]

# open_x, open_y : 시작하는 문의 (x, y)좌표
open_x, open_y = -1, -1
# close_x, close_y : 끝나는 문의 (x, y)좌표
close_x, close_y = -1, -1

for i in range(n):
    for j in range(n):
        if arr[i][j] == '#':
            if open_x == -1 and open_y == -1:
                open_x, open_y = i, j
            else:
                close_x, close_y = i, j

# check : 현재 i행 j열이고 dir방향으로 들어올 때 필요한 최소 거울의 갯수
check = [[[-1] * 4 for _ in range(n)] for _ in range(n)]
q = collections.deque()

# 시작 지점에서 시작 방향 설정
for a in range(4):
    q.append((open_x, open_y, a))
    check[open_x][open_y][a] = 0
    
while q:
    x, y, dir = q.popleft()
    # 현재 지점이 닫는 문이면 정답 출력 후 바로 종료
    if x == close_x and y == close_y:
        print(check[x][y][dir])
        break
    nx, ny = x + dx[dir], y + dy[dir]
    # 범위에 만족하는 경우
    if 0 <= nx < n and 0 <= ny < n:
    
        # 벽이 아닌 경우
        if arr[nx][ny] != '*':
        
            # 처음 방문하는 곳이거나 이전에 방문했던 점보다 더 적은 횟수로 갈 수 있다면
            # 상태공간 갱신 및 큐의 앞부분에 삽입 
            # 거울을 놓을 수 있어도 놓지 않는 경우거나 아예 거울을 놓을 수 없는 공간 두 가지 모두 고려가능
            if check[nx][ny][dir] == -1  or check[nx][ny][dir] > check[x][y][dir]:
                check[nx][ny][dir] = check[x][y][dir]
                q.appendleft((nx, ny, dir))
                
            # 거울을 놓는 경우
            if arr[nx][ny] == '!':
                # 방향이 북이거나 남이면 동,서로 반사
                # 이 때 거울을 설치하기 때문에 큐의 뒷부분에 삽입
                if dir < 2:
                    for n_dir in range(2, 4):
                        if check[nx][ny][n_dir] == -1 or check[nx][ny][n_dir] > check[x][y][dir] + 1:
                            check[nx][ny][n_dir] = check[x][y][dir] + 1
                            q.append((nx, ny, n_dir))
                            
                # 방향이 동이거나 서라면 남,북으로 반사
                # 이 때 거울을 설치하기 때문에 큐의 뒷부분에 삽입
                else:
                    for n_dir in range(2):
                        if check[nx][ny][n_dir] == -1 or check[nx][ny][n_dir] > check[x][y][dir] + 1:
                            check[nx][ny][n_dir] = check[x][y][dir] + 1
                            q.append((nx, ny, n_dir))