다익스트라

다익스트라는 그래프에서 '최소 비용', 그 중에서도 주어진 두 노드 사이의 최소 비용인 경로를 찾을 때 유용한 알고리즘이다.

• 시작 노드와 연결된 노드 중 비용이 가장 적게 드는 정점을 선택하고, 그와 연결된 정점들의 거리를 갱신해가면서 최소 비용인 거리를 탐색한다.
• 모든 가중치가 양수여야만 적용할 수 있다.
• 시간복잡도를 낮추기 위해 우선순위 큐를 이용하여 정렬하는 것이 좋다.

해킹

BOJ '해킹' 문제 보러가기

풀이 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int T, n, d, c;
int seconds[10005];

// 먼저 감염될 수 있으므로 & s>=0 -> 다익스트라

int main(){
    
    cin >> T;
    // 아래 내용을 T 만큼 반복
    for(int j=0;j<T;j++){
        // 1. 입력 받기
        pair<int,int> answer={1,0}; // n 최대치 * s 최대치 <= 21억 이라 int여도 OK
        vector<pair<int,int>> graph[10005];
        priority_queue<pair<int, int>> pq; // 최소 힙을 위해 pair<-소요 시간, 컴퓨터 번호>

        cin >> n >> d >> c;

        fill_n(seconds, n+5, 987654321); // 감염 시간 배열 초기화
        
        int a, b, s;
        for(int i=0;i<d;i++){
            cin >> a >> b >> s;
            graph[b].push_back({s,a}); // pair<소요 시간, 컴퓨터 번호>
        }

        // 2. 감염 시작 컴퓨터 표시
        seconds[c] = 0;
        pq.push({0, c});

        // 3. 우선 순위 큐를 이용해서 더 빠르게 감염되는 곳부터 먼저 방문
        while(!pq.empty()){
            int cur = pq.top().second;
            int curCost = -pq.top().first;
            pq.pop();

            if(graph[cur].size() == 0) break;

            // 4. 연결 컴퓨터의 감염 소요 시간 업데이트
            int minCost = 987654321;
            for(int i=0; i<graph[cur].size(); i++){
                int node = graph[cur][i].second;
                int nodeCost = graph[cur][i].first;
                if(seconds[node] > curCost + nodeCost){
                    seconds[node] = curCost + nodeCost;
                    minCost = min(minCost, seconds[node]);
                }
            }

            // 5. 나머지 연결 컴퓨터의 감염 소요 시간 업데이트
            for(int i=0; i< graph[cur].size();i++){
                int node = graph[cur][i].second;
                seconds[node] -=minCost;
                pq.push({-seconds[node],node});
            }

            // 6. 결과 업데이트
            answer.first++;
            answer.second+=minCost;
            
            
        }

        // 7. 정답 출력
        cout << answer.first << ' '<<answer.second<<"\n";
    }

    
}

예제는 출력할 수 있었지만 메모리 초과가 발생했다.

풀이 하지 못한 이유

1. 이번 문제는 스스로 풀 수 있을 것 같아서 약 2시간 동안 고민하였다. 구현 방안은 빠르게 잘 떠올린 듯 하나 어처구니 없는 실수(변수 선언 순서, 초기화 순서)로 쓸데 없이 시간을 많이 소요했다.
2. 메모리 초과가 발생하는데 관련 질문을 찾아보아도 그래프를 2차원 배열이 아닌 인접리스트로 구현해야한다는 글 밖에 찾을 수 없었다. 그런데 이미 나는 배열이 아닌데... 해당 부분에 대한 원인 탐색이 어려웠다.

참고 자료

• [ 다익스트라 알고리즘 ] 개념과 구현방법 (C++)
• [C++] 라이브러리, 우선순위 큐, 최대 힙, 최소 힙