너에게로 가는 가장 빠른길,,,

Dijkstra?

  • 다익스트라??! 이름부터 신기한 이 알고리즘은 그래프에서 출발점을 기준으로 모든 노드에 대한 최단길이를 구하게 도와주는 알고리즘입니다. 최단 길이를 구하게 도와주는 알고리즘은 3가지 정도가 존재하고, 우리는 오늘 그 중 하나인 다익스트라 알고리즘에 대해서 알아보도록 할 것입니다!
  • 너에게로 가는 가장 빠른길! 함께 알아보도록 합시다!

다익스트라 알고리즘이란

  • 다익스트라를 구현하기 앞서서 알고리즘이 어떻게 작동하는지 큰 틀에서 알아보도록 하겠습니다.
      1. 기준으로 삼은 노드를 정합니다.
      2. 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택하여 방문을 합니다.
      3. 선택한 노드를 기준으로 이동이 가능하고 , 아직 방문하지 않은  노드에 대해 거리를 갱신해주고, 2번을 반복하면 됩니다.
  • 즉, N개의 노드가 있다면 출발지를 제외한 N-1개의 노드로부터 인접한 노드의 거리를 갱신해주면, 각 노드로 가는 최단 거리를 알 수 있다는 겁니다.
  • 작동하는 방식 2번에서 알 수 있듯이, 매 루프마다 길이가 가장 짧은 노드를 고르기 때문에 기준을 삼은 노드는 이미 최단거리를 가지고 있음을 장담할 수 있습니다.
  • 그림을 보면서 설명을 쉽게 가져가도록 해봅시다! ^^

그림으로 보는 작동원리

  • 그림에서 사용되는 Priority Queue 는 Min Heap을 사용할 것이다. 들어가는 원소는 (최단거리, 노드번호) 입니다.

  • 현재 기준 노드 , 방문한 노드 , 가능한 간선 로 구분을 해놓았습니다. 가능한 간선은 방문하지 않는 노드에 관해서만 갈 수 있습니다! 그림을 보시죠!

    djk djk2

  • 매번 최단거리를 가지고 있는 노드가 선택이 되고, 방문하지 않았던 노드에 대해서만 거리를 측정해주면서 갱신해주면, 다익스트라 알고리즘이 완성이 된답니다!
  • 자, 그러면 그림으로 대충 이해를 해봤으니 코드로 구현을 하면서 더 알아보도록 합시다!

가장 짧은 노드를 선택?

  • 위의 그림에서는 알 수 있듯이 우리는 항상 작은 길이를 가지고 있는 노드를 선택해서 갱신을 해주어야 합니다. 만약 매번 탐색을 통해서 작은 길이를 가진 노드를 찾는 다면 O(노드갯수^2) 를 가지게 될 것입니다. 인터넷도 2초이상 못 기다리는 우리에게는 너무나 가혹한 효율성입니다. 따라서 우리는 그저 전체탐색을 하기보다는 힙 자료구조 를 사용해서 효율성을 높여보도록 할 것입니다!
  • C++에서는 힙 자료구조를 #include <queue> 에서 제공하는 priority_queue 자료구조가 위에서 필요한 역할을 해준다. 다만, C++에서는 Python과 다르게 Max Heap 을 제공하기 때문에 Min Heap 에 맞게 조정을 해줘야 한다.
  • priority_queue<pair<int, int>, vector<pair<int, int>> greater<pair<int, int>> () 로 최소힙을 완성시킬 수 있고, 매 루프마다 알아서 최소의 거리를 가진 노드가 pop이 된다. (거리, 노드) 순서로 자료구조에 넣어주어야 한다.

이동이 가능하고, 방문하지 않은?

  • 1번 노드에서 2번노드로 이동이 가능하다는 것을 우리는 아래의 2가지 방법으로 자료구조를 만들 수 있다.
    • 인접행렬
    • 인접리스트
  • 다만, 인접행렬(O(노드갯수^2))의 경우에는 매번 인접한 정점을 찾아야하므로 인접리스트(O(가능한후보))보다 매우 많은 시간이 들것이다. 따라서 우리는 자료구조 또한 매우 효율적인 인접리스트를 사용하도록 할 것이다.
  • 인접리스트를 쉽게 구현할 수 있도록 우리는 #include <map> 와 #include <vector> 활용할 것이다. map<int, vector<pair<int,int>>> 을 사용하여 key의 값으로는 출발지점 노드번호를 넣고, vector에는 (갈 수 있는 노드, 비용)을 넣을 것이다.
  • 방문여부는 #include <vector>를 활용할 것이다. vector<int, bool>을 통해 방문하는 노드를 체크해 줄 것이다.
  • 자 그럼, 구현에 필요한 기초 재료들은 준비가 되었고! 구현된 코드를 통해 알아보도록 하자!

코드

다익스트라와 연관된 문제

  • 백준 1753 - 최단 경로
    • 방향그래프이고, 정점 사이에 여러개의 간선이 존재함을 인지하고 풀어보자
  • 백준 1504 - 특정한 최단 경로
    • 무향그래프이고, 1번 정점에서 N번 정점에 도착할 때 v1과 v2 정점을 무조건 방문해야 한다.
    • 갈 수 있는 방법은 2가지가 있다.
      • 1 -> v1 -> v2 -> N
      • 1 -> v2 -> v1 -> N
  • 백준 4485 - 녹색 옷 입은 애가 젤다지?
    • 정점이 아니라, 행렬로 정보들이 주어진다. 이것을 적절한 자료구조로 변환을 해줘야 한다.
    • 다익스트라로 풀 수 있고, bfs를 통해 갱신해주면서 풀 수도 있다.
  • 백준 1238 - 파티
    • 파티가 열리는 마을까지 가서 돌아오는 합이 가장 작은 놈을 골라야한다.
    • 기준을 잡고 다익스트라를 돌려주어야 한다.
  • 위의 문제들은 조만간 포스팅을 하도록 하겠다!