[항해99 취업 리부트 코스 학습일지] Day 21 - 다익스트라

오늘 목표

• TIL 작성
• 필수 문제 풀기

---

학습한 것

오늘은 다익스트라 알고리즘에 대해서 학습했다. 

다익스트라 알고리즘은 특정 노드에서 다른 노드까지의 최단 경로를 찾는 그래프 탐색 알고리즘이다. 가중치가 있는 그래프에서 대표적으로 사용하며 다익스트라의 개념에 대해서 이해하기 위해서는 아래 3가지 개념 정도는 미리 알고 있는게 좋다.

• 그래프와 그래프 탐색에 대한 이해(DFS, BFS)
• 그리디 알고리즘 : 방문하지 않은 노드 중 가장 비용이 적은 노드 선택.
• DP : 해당 노드로부터 갈 수 있는 노드들의 비용을 지속적으로 갱신.

또한 다익스트라 알고리즘은 최단 경로를 찾는 방식에서는 효율적이고 좋은 알고리즘이지만, 만약 가중치가 음수인 경우에는 정상적으로 동작하지 않는다.

전체적인 동작 과정은 다음과 같다.

1. 시작 노드를 설정하고 특정 노드까지의 최소 비용을 저장할 최단 거리 테이블을 초기화한다.
   1. 최소 비용을 저장할 공간의 값은 시작은 모두 INF와 같이 매우 큰 값으로 저장한다.
   2. 시작 노드의 비용은 0, 직전 노드는 자기 자신으로 설정한다.
2. 방문하지 않은 노드 중 최소 비용이 가장 작은 노드를 선택한다.
   1. 각 노드까지 가는 최소 비용과 현재까지 구한 최소 비용을 비교해 작은 값을 최소 비용으로 갱신한다.
   2. 직전 노드도 같이 갱신한다.
3. 노드 개수에서 1을 뺀 만큼을 계속 반복한다.

from heapq import *

def dijikstra(graph, start):
    """
    [input]
    graph: 인접 리스트 형태의 그래프.
    graph[i] = [(j, cost), ...]는 i번 정점에서 j번 정점까지의 거리가 cost라는 의미
    
    start: 시작 정점의 번호

    [output]
    start 정점에서 각 정점까지의 최단 거리를 반환
    """

    INF = float('inf') 

    # 시작점을 제외한 모든 정점까지의 거리를 무한대로 설정.
    dist = [INF] * len(graph)
    dist[start] = 0

    # 우선순위 큐에 (거리, 정점)을 넣어준다.
    # 시작 정점은 거리가 0이므로 (0, start)
    q = [(0, start)]

    # 우선순위 큐가 빌 때까지 계속해서 수행
    while q:
        # 우선순위 큐에서 가장 거리가 짧은 정점을 꺼낸다
        cost, idx = heappop(q)
        # 이미 처리된 정점(이미 최단 거리를 구한 정점)이라면 무시
        if dist[idx] < cost:
            continue

        # 현재 정점에서 갈 수 있는 모든 정점을 확인한다.
        for adj, d in graph[idx]:
            if dist[adj] > cost + d:
                dist[adj] = cost + d
                heappush(q, (dist[adj], adj))

    return dist

---

좋았던 점

다익스트라 알고리즘 자체가 어느 정도 정해진 형식이 있기 때문에 이해를 하고 나면 어느 정도 익숙하게 다룰 수 있다면 괜찮지만 처음 학습할 때의 난이도가 상당한 것 같다. 멘토님께서도 다익스트라는 정해진 틀에서 크게 벗어나지 않으니 익숙해진다면 금방 풀 수 있을거라 말씀하셨기에 일단 외우면서 학습 중이다.

---

아쉬웠던 점

알고리즘에 대한 학습도 좋만 점차 주력 언어나 프레임워크에 대한 실력이 감퇴하는 것 같아 걱정이다. 조금씩이지만 언어에 대한 학습이나 프레임워크에 대한 학습을 늘려가야겠다.

---

항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠입니다.

IT 커리어 성장 코스 항해99, 개발자 취업부터 현직자 코스까지