다익스트라 알고리즘

개요

백준 1753번 최단경로 문제에 대한 다익스트라 알고리즘 풀이 입니다.

다익스트라(Dijkstra) 알고리즘은 최단 경로를 구할 때 자주 사용되는 알고리즘입니다.

특히, 가중치가 양수인 그래프에서 출발 노드로부터 다른 모든 노드까지의 최단 경로를 구할 수 있습니다.

먼저 인접행렬 방식으로 다익스트라 알고리즘을 구현하는 코드를 설명하고 인접리스트도 같이 살펴보겠습니다.

 

소스코드

방향 그래프가 아래 그림과 같다면 인접행렬과 인접리스트를 정리.

위 그림의 오른쪽 인접리스트 중 1:(1,2), (2,3) 의 의미는 1번 노드에서 (2번노드, 비용2), (3번노드, 비용3)의 의미.

(노드인덱스를 0번 기준으로 작성하다보니 1만큼 작게 표시되었습니다. 😓)

 

먼저 인접행렬로 코드작성.

# adjacency matrix, 인접행렬, 2차원 배열로 구현
import heapq

def dijkstra_matrix(g, start, n):    
    dist = [float('inf') for _ in range(n)]
    dist[start] = 0
    visited = [False for _ in range(n)]
    lst = [(0, start)]  # (거리, 노드)

    while lst:
        d, i = heapq.heappop(lst) # 가장 짧은 거리의 노드 꺼내기
        if visited[i]:
            continue
        visited[i] = True

        for v in range(n):
            if g[i][v] != 0:  # 간선이 존재할 때
                if dist[v] > d + g[i][v]:
                    dist[v] = d + g[i][v]
                    heapq.heappush(lst, (dist[v], v))

    return dist

# 정점, 간선 수
V, E = map(int, input().split(' '))
# 시작정점
K = int(input())

# 인접행렬 초기화
graph = [[0 for _ in range(V)] for _ in range(V)]

for i in range(E):
    u, v, w = map(int, input().split(' '))
    u -=1
    v -=1
    graph[u][v] = w

print(graph)

result = dijkstra_matrix(graph, K-1, V) 
#print(result)

for i in result:
    if i==float('inf'):
        print('INF')
    else:
        print(i)
        

풀이

기본 개념 정리

• 그래프(Graph): 정점(V)과 간선(E)으로 구성된 구조.

• 인접행렬(Adjacency Matrix): 그래프를 2차원 배열로 표현. g[i][j]는 i번 정점에서 j번 정점으로 가는 가중치.

• 다익스트라 알고리즘: 하나의 시작 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘.

 

입력처리

V, E = map(int, input().split())  # 정점 개수 V, 간선 개수 E
K = int(input())                  # 시작 정점 번호

• 사용자로부터 정점 수, 간선 수, 시작 정점을 입력.

• 정점 번호는 1부터 시작하므로, 나중에 인덱스를 맞추기 위해 -1 처리.

 

인접행렬 만들기

graph = [[0 for _ in range(V)] for _ in range(V)]

• V x V 크기의 2차원 배열을 만들어 인접행렬을 초기화.

• 값이 0이면 두 정점 사이에 간선이 없다는 의미.

 

for i in range(E):
    u, v, w = map(int, input().split(' '))
    u -=1
    v -=1
    graph[u][v] = w

• 간선 정보를 입력받아 인접행렬에 저장.

• 방향이 있는 그래프라면 graph[v][u] = w 처리 X

• 예를 들어 1 2 4를 입력, 1번 정점에서 2번 정점으로 가는 비용이 4.

 

다익스트라 함수 설명

def dijkstra_matrix(g, start, n):

• g: 인접행렬

• start: 시작 정점

• n: 전체 정점 개수 

 

초기화

dist = [float('inf')] * n     # 거리 배열: 무한대로 초기화
dist[start] = 0               # 시작 정점은 0으로 설정

visited = [False] * n         # 방문 여부 체크
lst = [(0, start)]            # 최소 힙: (거리, 노드)

• dist[i]: 시작점에서 i번 정점까지의 최소 거리

• visited[i]: 이미 방문한 정점인지 확인

• lst: 힙 구조를 사용하여 가장 짧은 거리의 노드를 빠르게 찾음 

 

핵심 반복문

while lst:
    d, i = heapq.heappop(lst)  # 가장 가까운 정점 꺼내기

    if visited[i]:
        continue               # 이미 방문했으면 패스
    visited[i] = True

• heapq.heappop()으로 현재까지 가장 짧은 거리의 노드얻기.

 

이웃 노드 확인

for v in range(n):
    if g[i][v] != 0:                         # 간선이 존재하면
        if dist[v] > d + g[i][v]:            # 더 짧은 경로 발견
            dist[v] = d + g[i][v]
            heapq.heappush(lst, (dist[v], v))

• g[i][v] != 0 현재 노드 i에서 v로 가는 길이 있는지 확인.

• 만약 기존 거리보다 더 짧은 길 발견 시 dist[v]를 갱신, 다시 힙에 푸시. 

 

출력

for i in result:
    if i == float('inf'):
        print('INF')
    else:
        print(i)

• 거리가 무한대라면 도달할 수 없는 정점, INF 출력.

• 그 외에는 최단 거리 출력.

 

 

예시 입,출력

입력 첫째 줄 5 6 : 정점개수 5, 간선개수 6

입력 둘째 줄 1 : 시작 정점 번호

입력 셋째 줄 5 1 1 : 5번정점에서 1번 정점까지 거리 1

입력 넷째 줄 1 2 2 : 1번정점에서 2번 정점까지 거리 2

나머지 동일절차... (유방향 그래프임을 주의)

출력 첫째 줄 0 : 1번정점에서 1번정점까지 최단거리

출력 둘째 줄 2 : 1번정점에서 2번정점까지 최단거리 

출력 셋째 줄 3 : 1번정점에서 3번정점까지 최단거리 

출력 넷째 줄 7 : 1번정점에서 4번정점까지 최단거리  

출력 다섯번째 줄 INF : 1번정점에서 5번정점까지 경로없음

 

결과는 맞지만 백준 제출하면 "메모리초과" 오류.

아래는 인접리스트로 작성된 코드 (정답) 

 

인접리스트 소스코드

# adjacency list, 인접리스트
import sys
import heapq

def dijkstra_matrix(g, start, n):    
    dist = [float('inf') for _ in range(n)]
    dist[start] = 0
    visited = [False for _ in range(n)]
    lst = [(0, start)]  # (거리, 노드)

    while lst:
        d, i = heapq.heappop(lst) # 가장 짧은 거리의 노드 꺼내기
        if visited[i]:
            continue
        visited[i] = True

        for v, w in g[i]:            
            if dist[v] > d + w:
                dist[v] = d + w
                heapq.heappush(lst, (dist[v], v))

    return dist

# 정점, 간선 수
V, E = map(int, sys.stdin.readline().rstrip().split(' '))
# 시작정점
K = int(sys.stdin.readline().rstrip())

# 인접리스트 초기화
graph = [[] for _ in range(V)]

for i in range(E):
    u, v, w = map(int, sys.stdin.readline().rstrip().split(' '))
    u -=1
    v -=1
    graph[u].append((v, w)) # u에서 v로 가는 가중치 w

print(graph)

result = dijkstra_matrix(graph, K-1, V) 
#print(result)

for i in result:
    if i==float('inf'):
        #print('INF')
        sys.stdout.write(f'INF\n')
    else:
        #print(i)
        sys.stdout.write(f'{i}\n')
        
        

 

인접행렬 VS 인접리스트?  

항목	인접 행렬 (Adjacency Matrix)	인접 리스트 (Adjacency List)
공간 복잡도	O(V²)	O(V + E)
간선 탐색 속도	빠름 (O(1))	느림 (O(연결된 노드 수))
메모리 효율성	낮음 (불필요한 0도 저장)	높음 (필요한 간선만 저장)
구현 난이도	간단	조금 복잡
대규모 그래프 처리	비효율적	효율적
사용 추천 경우	정점 수 작고, 간선 수 많을 때	정점 수 많고, 간선 수 적을 때
실전 코딩 테스트 활용도	거의 사용 안함	가장 많이 사용

 

감사합니다.