[BOJ] Python 백준 4485번 녹색 옷 입은 애가 젤다지? 골드 4

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

4485번: 녹색 옷 입은 애가 젤다지?

 

문제 풀이

---

왼쪽 위칸인 [0,0]에서 출발 후 오른쪽 아래칸인 [N-1, N-1]에 도착하는 경로를 생각하는 그래프 탐색 문제였다.

 

다만 흔히 Queue나 Stack을 이용하여 BFS, DFS로 탐색하는 방법이 아닌 Priority Queue를 사용한 다익스트라 문제였다.

 

이 문제에서 중요한 점은 거리의 최소가 아니라 비용, 즉 가중치의 최소가 중요하기 때문이다.

 

상당히 돌아가는 경로라 하더라도 비용이 최소면 해당 경로를 택하기 때문에 가중치의 합을 기준으로 최소 비용 경로를 고려해야 한다.

 

Priority Queue를 이용한 원리는 다음과 같다.

 

먼저 시작 노드에서 이동 가능한 노드를 가중치의 합과 함께 Priority Queue에 넣는다.

 

가중치의 합이 가장 작은 노드를 선택한 뒤 해당 노드에서 이동 가능한 노드를 가중치의 합과 함께 Priority Queue에 넣는 행동을 [N-1, N-1]에 도착할 때까지 반복한다.

 

[N-1, N-1]에 도착하면 해당 가중치를 저장하고 반복을 종료한다.

 

한 번은 중간에 이동 가능한 노드인지 체크하는 과정에서 이미 방문한 노드가 최소 가중치의 합을 보장하는지 의문을 품는 질문을 본 적이 있었는데 결론부터 말하자면 각 노드에서 가장 먼저 선택되었을 때의 가중치가 최소다.

 

Priority Queue를 통해 매번 가장 작은 가중치의 합을 선택하기 때문에 두 번째 방문할 때는 같거나 클 수밖에 없기 때문이다.

 

이제 전체 코드를 통해 설명하도록 하겠다.

 

import heapq
inf = float('INF')
dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]
res_num = 1
while True:
    n = int(input())
    if n == 0:
        break
    else:
        graph = []
        queue = []
        res = [[inf for i in range(n)]for j in range(n)]
        for i in range(n):
            graph.append(list(map(int, input().split())))
        heapq.heappush(queue, (graph[0][0], 0, 0))
        res[0][0] = graph[0][0]
        while len(queue) > 0:
            temp = heapq.heappop(queue)
            if temp[1] == n-1 and temp[2] == n-1:
                break

            for i in range(len(dir)):
                dy = temp[1]+dir[i][0]
                dx = temp[2]+dir[i][1]
                if 0 <= dy < n and 0 <= dx < n and res[dy][dx] > temp[0]+graph[dy][dx]:
                    res[dy][dx] = temp[0]+graph[dy][dx]
                    heapq.heappush(queue, (temp[0]+graph[dy][dx], dy, dx))
        print("Problem %d: %d" %(res_num,res[n-1][n-1]))
        res_num += 1

 

4번째 줄까지는 Priority Queue를 사용하기 위한 heapq 선언, 방문하지 않은 노드는 무한대 선언, 노드의 방향 선언, 문제 번호 선언이다.

 

5번째 줄의 while문을 통해 0을 입력받을 때까지 반복적으로 문제를 처리했다.

 

12번째 줄의 res는 노드의 최솟값을 갱신하는 리스트로 마지막에 res [N-1][N-1]을 출력하면 된다.

 

15번째 줄은 시작 노드의 가중치와 y좌표, x좌표 순서대로 넣음으로써 자동으로 MinHeap 구조인 heapq에서 최소 가중치를 꺼내도록 하였다.

 

18번째 줄의 반복문은 Priority Queue가 빌 때까지 계속 원소를 꺼내는 작업을 하는데 도착지점에 도달한다면 탈출하도록 구현하였다.

 

방향 탐색을 하기 위해 22번째 줄에서 이동 가능한 노드인지 체크한 후 Priority Queue에 넣어주도록 구현하였다.

 

결과 화면

 

구현 방법이나 알고리즘 측면에서 어려운 문제는 아니었지만 우선순위 큐를 거의 사용해보지 않았다면 충분히 떠올리기 어려울 수 있다고 생각한다.

 

필자 또한 다양한 그래프 문제를 경험해봤지만 습관처럼 BFS, DFS를 사용했기에 해당 문제를 보고 바로 Priority Queue를 떠올리진 못했다.

 

보다 유연하고 다양하게 생각하도록 노력하는 게 중요한 것 같다.