Programming/Algorithm

[c++] 백준 1753번 오답노트 :: 다익스트라 구현

하일리킴 2025. 4. 6. 14:55

다익스트라(Dijkstra) 알고리즘이란?

- 최단 경로를 구할 때 사용한다.

- 한 정점에서 다른 모든 정점으로 가는 최단 경로의 비용을 저장한다.

- 다이내믹프로그래밍이다. 왜냐하면 A에서 B로의 최단 경로는 A에서 다른 곳들로의 최단경로들로 구성되어 있기 때문이다.

- 즉 전체의 문제가 부분의 문제를 포함하므로 다이내믹프로그래밍으로 풀 수 있다.

- 한 경로의 최단거리를 구할 때, 이전까지 구했던 최단거리들을 사용한다.

 

다익스트라 알고리즘의 구현 방법

1. 정점과 간선정보를 저장하는 2차원 배열이 필요하다.

2. 시작 정점이 정해지면 그 정점으로부터 다른 정점까지의 거리를 벡터로 표현한다.

3. 가장 비용이 작은 정점을 선택한다. 그 정점을 거쳐서 다른 정점으로 가는 비용이 원래 값보다 작다면 벡터의 값을 업데이트 한다.

4. 선택되지 않은 정점중 가장 비용이 작은 것을 선택한 후 3을 반복한다.

 

 

백준 1753번 문제 풀이

문제 링크 :

 

1753번: 최단경로

 

 

 

거리 벡터를 priority queue로 표현하는 이유는 priority queue는 자료를 이미 정렬된 상태로 저장하고 있기 때문이다.

과정 3에서 비용이 가장 작은 정점을 선택하기 위해서 최솟값을 찾아 나설 필요가 없다. 

 

 

 

 

데이터구조

int d[MAXV];
vector<pair<int, int>> a[MAXV+5];

- 시작 정점으로부터 다른 정점까지 거리정보(계속 업데이트하기 위함)는 배열 d에 저장한다.

- 처음에 입력받은 모든 정점/간선 정보는 벡터 배열 a에 저장한다.

각 배열의 인덱스 a[i] 의 i는 정점을 의미한다.

a[i]는 i에서 모든 정점으로 가는 거리 비용을 벡터로 저장한다.

벡터의 각 원소는 pair이다.

pair의 first는 비용이고, second는 다른 정점이다.  

a[1] 이라는 벡터에 <5, 3>이라는 원소가 있다면.

1에서 3으로 가는 비용이 5라는 뜻이다.

벡터 원소의 first에 정점이 아니라 비용을 저장하는 이유는, 나중에 priority queue로 저장할 때 비용이 최소가 되는 순으로 정렬하기 위함이다. 

 

입출력 처리, 데이터 전처리

int main(void)
{

    //cin.tie(NULL);
    cin >> v >> e;
    cin >> k;
   // cout << a[1].size();
    // 메모리를 INF로 초기화하자. . . !
    for (int i = 1; i <= v; i++) {
        d[i] = INF;
        a[i].push_back(make_pair(i, 0));
    }

    for (int i = 0; i < e; i++) {
        int p, q, w;
        cin >> p>> q>> w;
        a[p].push_back(make_pair(q, w));
       
    }


...
...
...

 

v : 정점(vertex)의 갯수

e : 간선(edge)의 갯수

k : 시작 정점

 

d에는 다익스트라로 구한 최적화된 경로가 업데이트될 예정이다.

사용하기 전에 미리 INF로 초기화 해둔다. INF는 예상하는 가장 큰 수이다. 

처음에는 거리가 무한대라고 생각한다.

a에는 문제에서 주어진 기본 연결 정보를 저장한다. 

i에서 i로 가는 거리는 0으로 취급한다.

edge 수 만큼 p에서 q로 가는 거리 w를 입력받아 a를채운다.

    dijkstra(k);  // starting point k
    for (int i = 1; i <= v; i++) {
        if (d[i] == INF) cout << "INF" << "\n";
        else cout << d[i] << "\n";
    }
    return 0;
}

 

dijkstra 함수로 문제를 푼다.

k를 인자로 넘겨 함수를 실행하고 나면 거리정보 d가 완정된다.

v만큼 loop를 돌며 정답을 프린트한다.

 

 

dijkstra 알고리즘 구현

void dijkstra(int start) {
    d[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; // 힙 구조
    pq.push(make_pair(0, start));
    //가까운 순서대로 처리하므로 큐를 사용.
    while (!pq.empty()) {
        int current = pq.top().second;
        int distance = pq.top().first;
        pq.pop();
        // 최단거리가 아닌 경우 스킵 
        if (d[current] < distance) continue;
        
        for (int i = 0; i < a[current].size(); i++) {
            //선택된 노드의 인접 노드
            int next = a[current][i].second;
            // 선택된 노드를 인접 노드로 거쳐서 가는 비용
            int nextDistance = distance + a[current][i].first;
            // 기존의 최소 비용보다 더 저렴하다면 교체
            if (nextDistance < d[next]) {
                d[next] = nextDistance;
                pq.push(make_pair(nextDistance, next));
            }

        }
    }
}

1) priority queue pq를 사용한다.

이 자료구조에는 위 '알고리즘 구현'의 3번에서 선택된 노드들을 push할 것이다.

2) pq에 push하는 기준이 있다.

첫번째로 타겟 정점인 start를 push한다. start에서 start로 가는 비용은 당연 0이다.

start에서 다른 노드들로 가는 정보는 a[start]에 저장되어 있다.

start에서 연결된 노드들은 i로순회한다.

i를 거쳐서 가는 비용이 더저렴하다면 거리 비용을 업데이트하고, 업데이트한 정점을 다시 queue에 넣는다.

 

중요한 부분은 이부분이다.

    priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; // 힙 구조

priority queue는 first가 큰 순서대로 priority를 부여한다.

따라서 나는 거리가 작은 순으로 정렬하고 싶으므로

최소 힙 구현을 위해서는 정렬 기준을 greater로 바꿔줘야 한다. 

(lesser에서 greater로 엘리먼트가 정렬된다고 생각)