백준 2665 <미로 만들기> Python

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

---

다익스트라 알고리즘을 사용해 풀 수 있는 문제입니다.

 

이동 가능한 방향을 탐색할 때, 이동할 노드가 벽이 아니라면 해당 노드를 바꿀 필요가 없기 때문에 그대로 큐에 넣어주지만, 해당 노드가 벽이라면 우선 바꾸고 이동한 것으로 간주해 큐에 넣어줍니다. 이런 식으로 탐색을 진행하면 모든 노드를 최소 변환 횟수와 함께 탐색할 수 있습니다.

 

큐를 최소힙으로 사용하는 이유는 바꾼 횟수가 적은 순서로 탐색을 해주기 위함인데, 바꾼 횟수가 더 많고 같은 위치를 탐색할 경우 더 적은 횟수로 먼저 탐색했기 때문에 자동으로 걸러주기 때문입니다.

 

최소힙이 아닌 데크를 사용할 경우, BFS처럼 풀 수도 있지만 바꾼 횟수가 높은 탐색경우가 먼저 같은 위치에 도달하는 경우가 발생해 시간적인 손해가 발생합니다.

---

import sys
import heapq as hq

input = sys.stdin.readline


def solution(n, rooms):
    # 이동 방향
    move_dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    # 방문 목록
    visited = [[float('inf') for _ in range(n)] for __ in range(n)]
    # 큐 / [[바꾼 수, 인덱스] ... ]
    q = [[0, 0, 0]]
    visited[0][0] = 0
    # 순회
    while q:
        # 바꾼 수 / 인덱스
        changed, now_x, now_y = hq.heappop(q)
        # 바꾼 수가 더 많으면 패스
        if changed > visited[now_x][now_y]:
            continue
        
        # 이동 가능 위치 순회
        for x, y in move_dirs:
            # 다음 인덱스
            next_x = now_x + x
            next_y = now_y + y
            # 범위 내고
            if (next_x >= 0 and next_x < n) and (next_y >= 0 and next_y < n):
                # 벽이 아니면서 더 적게 바꾸고 방문할 수 있으면
                if (rooms[next_x][next_y] == '1') and (changed < visited[next_x][next_y]):
                    # 방문
                    visited[next_x][next_y] = changed
                    # 큐에 추가
                    hq.heappush(q, [changed, next_x, next_y])
                
                # 벽인데 더 적게 바꾸고 방문할 수 있으면
                elif (rooms[next_x][next_y] == '0') and (changed + 1 < visited[next_x][next_y]):
                    # 방문
                    visited[next_x][next_y] = changed + 1
                    # 큐에 추가
                    hq.heappush(q, [changed+1, next_x, next_y])
        
    print(visited[-1][-1])


# 입력
n = int(input().strip())
rooms = [input().strip() for _ in range(n)]

solution(n, rooms)