[백준/다익스트라] 4485번 : 녹색 옷 입은 애가 젤다지?

- 링크 : www.acmicpc.net/problem/4485

 

이 문제는 bfs로 진행하는데 각 노드에는 숫자가 있다. 각 노드를 지날 때마다 노드 값이 더해지는데, (0,0)에서 (n - 1, n - 1)까지 가면서 지나간 노드의 값의 최솟값을 구하는 문제다.

바로 bfs문제라는 것은 떠올랐지만, 다음 노드로 넘어갈 때 최소값인 경우를 고려해야하기 때문에 heap을 이용한 다익스트라를 구현해야함은 떠오르지 않았다. 다익스트라는 몇 번을 풀어도 머리에 잘 안 남는 것 같다 흑ㅠ

 

1. distance(n x n 크기) 행렬 이용하기

문제를 풀면서 잘 안 풀렸던 부분은 heap을 이용해야하는 것은 알겠는데, 그럼 heappop 값이 상하좌우에 있는 값이 아닌 저 멀리 떨어진 값이 나오면 어떻게 구분할 수 있을지 잘 몰랐다. 아래 코드에서도 확인되겠지만, 최댓값(1e9)로 이루어진 distance 행렬을 이용하면 된다. 

 

2. 노드 재방문 여부는 체크하지 않아도 된다.

경로를 지나다가 방문했던 노드를 지나는 게 최단 경로가 된다면 그냥 지나가도 되기 때문에 visit 행렬로 따로 방문 여부를 체크하지 않아도 된다. 최종 목표는 목표 지점까지 최솟값으로 가는 것이다!

 

 

정답 풀이

import heapq 

def dijkstra() :
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    queue = [[matrix[0][0], 0, 0]]
    distance = [[INF] * n for _ in range(n)]
    distance[0][0] = 0
    
    while queue:
        value, x, y = heapq.heappop(queue)

        if x == n - 1 and y == n - 1:
            print("Problem {0}: {1}".format(index, distance[x][y]))
            break
            
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                new_value = value + matrix[nx][ny]
                
                if new_value < distance[nx][ny]:
                    distance[nx][ny] = new_value
                    heapq.heappush(queue, [new_value, nx, ny])

INF = 1e9
index = 1 
while True : 
    n = int(input())
    
    if n == 0:
        break
    
    matrix = [list(map(int, input().split())) for _ in range(n)]
    
    dijkstra()
    index += 1

 

 

Reference

참고 블로그 : https://bbbyung2.tistory.com/60