백준 4485번 바로가기

📌다익스트라 알고리즘(Dijkstra Algorithm>

음의 가중치가 없는 그래프에서 한 정점에서 모든 정점까지의 최단경로를 모두 구하는 알고리즘이다.

기본적인 로직은 다음과 같다.

• 출발 노드를 설정한다.
• 거리를 저장할 테이블을 초기화시킨다.
• 현재 위치한 노드의 인접 노드로 넘어가는 가중치를 테이블에 저장한다.
• 만약 다른 노드를 거쳐서 해당 노드로 도달하는것이 가중치가 더 낮다면, 테이블을 업데이트한다.
• 위 과정을 반복해서 가장 짧은 경로만 테이블에 저장한다.

대부분 우선순위 큐를 이용해서 다익스트라 알고리즘을 구현한다.

---

📌백준 4485 녹색 옷 입은 애가 젤다지?

테스트 케이스 별로 N*N크기의 그래프가 주어지고, 각 위치에는 가중치가 주어진다. 이때, (0,0)의 위치에서 (N-1,N-1)까지 도달하는데 드는 최소비용을 구하는 문제라고 생각하면 된다.

그래프가 맵의 형태로 주어졌다. 이럴 때는 BFS문제를 풀때 x방향과 y방향을 각각 변경해 상하좌우로 움직이듯 구현했던 알고리즘을 응용하면 된다.

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

그래프를 입력받고, 그래프의 크기만큼 최단경로테이블도 초기화해준다.

    for i in range(n):
        graph.append(list(map(int, input().split())))

    dist = [[inf for i in range(n)] for j in range(n)]

그리고 다익스트라 알고리즘을 구현한다. Python에서는 heapq라는 라이브러리를 이용해서 우선순위 큐를 사용한다.

def dijkstra(t, graph, dist):
    que = [] #배열 생성
    dist[0][0] = graph[0][0] #시작 위치의 가중치

    heapq.heappush(que, (dist[0][0], 0, 0)) #시작 위치와 그 가중치를 우선순위 큐 형태로 배열에 추가

    while que:
        cost, x, y = heapq.heappop(que) #각각 현재 노드의 가중치와 x좌표, y좌표

        if dist[x][y] < cost: #만약 바로 이동하는 거리가 더 짧을 경우
            continue

        for i in range(4): #상,하,좌,우 4번
            nx = dx[i] + x 
            ny = dy[i] + y
            if n > nx >= 0 and n > ny >= 0 : #그래프를 벗어나지 않을 때
                temp = cost + graph[nx][ny] 
                if temp < dist[nx][ny]: #만약 다른 곳을 들렸다 가는 경우가 더 빠른경우
                    dist[nx][ny] = temp #테이블 업데이트
                    heapq.heappush(que, (temp, nx, ny)) #현재 노드를 우선순위 큐 배열에 추가

이렇게 시작지점부터 다른 모든 노드까지의 최소비용이 모두 구해져서 dist 테이블에 저장되었다.

이제 각 테스트케이스별로 (N-1, N-1)까지 의 거리를 출력하면 정답이다.

전체코드

import sys
input = sys.stdin.readline
import heapq
dx = [-1, 0 ,1 ,0]
dy = [0, 1, 0, -1]
inf = int(1e9)

def dijkstra(t, graph, dist):
    que = []
    dist[0][0] = graph[0][0]

    heapq.heappush(que, (dist[0][0], 0, 0))

    while que:
        cost, x, y = heapq.heappop(que)

        if dist[x][y] < cost:
            continue

        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if n > nx >= 0 and n > ny >= 0 :
                temp = cost + graph[nx][ny]
                if temp < dist[nx][ny]:
                    dist[nx][ny] = temp
                    heapq.heappush(que, (temp, nx, ny))

    print('Problem {}: {}'.format(t, dist[n - 1][n - 1]))


t = 1

while 1:
    n = int(input())
    graph = []
    if not n:
        break

    for i in range(n):
        graph.append(list(map(int, input().split())))

    dist = [[inf for i in range(n)] for j in range(n)]
    dijkstra(t, graph, dist)

    t += 1

---

📌고찰

• 그래프 탐색은 알고리즘을 알고 있다면, 그 알고리즘을 응용해서 쉽게 문제를 해결 할 수 있다.
• 알고리즘을 직접 구현해보고, 로직을 머릿속으로 이해하는 과정이 필요하다.