99클럽 코테 스터디 3일차 TIL + 다익스트라 알고리즘

❇️오늘의 학습 키워드 : 다익스트라 알고리즘

 

다익스트라 알고리즘?

- 가중치가 있는 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘

다익스트라 알고리즘의 동작 원리

    (1) 출발 지점(시작 노드)의 거리를 0으로, 나머지 노드들의 거리는 무한대(INF)로 설정

    (2) 우선순위 큐를 활용해 현재 가장 짧은 거리의 노드를 선택하고, 해당 노드를 중심으로 주변 노드들의 거리 갱신

    (3) 모든 노드를 방문할 때까지 반복

다익스트라라 알고리즘의 특징

- 우선순위 큐 사용시 시간복잡도는 O(ElogV)

- 음수 가중치가 없는 그래프에서 가장 효율적으로 작동

다익스트라 알고리즘에서 우선순위 큐 기능을 활용하는 이유?

- 최소 힙 자료구조로, 가장 작은 값이 항상 맨 앞에 오도록 정렬된 큐임!
    -> 현재까지 계산된 가장 짧은 거리를 먼저 확인하면서 진행해야 효율적임

다익스트라 알고리즘 코드 예제

import heapq
import sys
input = sys.stdin.readline

# 노드와 간선의 수 입력받기
v, e = map(int, input().split())
start = int(input())  # 시작 노드 번호

# 그래프 초기화 및 거리 배열 설정
graph = [[] for _ in range(v + 1)]
distance = [float('inf')] * (v + 1)

# 간선 정보 입력받기
for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))  # a 노드에서 b 노드로 가는 비용이 c

# 다익스트라 알고리즘 함수
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))  # 시작 노드 초기화
    distance[start] = 0

    while q:
        w, node = heapq.heappop(q) # 가중치와 노드인덱스 빼오기
        for nxt, weight in graph[node]:
            # 1. 각각의 노드에 값을 업데이트
            # 2. 만약에 여러 경로가 있다면 min 비교!
            # 3. 시작점으로부터 거리를 봐서, 짧은 순서대로 탐색! (오염방지)
            if distance[node] + weight < distance[nxt]: # 인접한 노드를 거쳐서 다음으로 가기(현재까지의 최솟값+가중치) vs 다음까지 스트레이트로 가기
                distance[nxt] = distance[node] + weight
                heapq.heappush(q,[distance[nxt],nxt])

# 다익스트라 알고리즘 수행
dijkstra(start)

# 모든 노드로의 최단 거리 출력
for i in range(1, v + 1):
    if distance[i] == float('inf'):
        print("INF")  # 도달할 수 없는 경우
    else:
        print(distance[i])

❇️오늘의 회고

  - 항해99 코테스터디 3일차 문제에서 1, 2일차에 공부했던 BFS 및 플로이드-워셜 알고리즘을 복습하고, 추가로 다익스트라 개념을 학습했다.

  - 다익스트라 알고리즘을 이용하는 문제를 많이 풀어서 체화시킬 것!

  - 현재노드인덱스에 (인접노드인덱스, 가중치) 이렇게 쌍으로 묶어서 저장하는 것에 유의한다!

  - 다익스트라 알고리즘을 이용하려면 음수 가중치가 없어야 한다는 것을 잊지 말자! ☺️