[프로그래머스/Level 3] 섬 연결하기 (C++)

programmers.co.kr/learn/courses/30/lessons/42861

코딩테스트 연습 - 섬 연결하기

다익스트라를 이용하여 해결하였습니다. 다만 시작점에서 각 정점까지의 누적 최단거리가 아니라, 해당 노드를 한번만 지나고 그 값이 최단거리가 되어야 합니다. 이렇게 되면 시작점이 어디냐에 따라 최소값이 다르게 나올 수 있기 때문에, 시작점을 0부터 n까지 모두 진행해보면서 어떤 시작점으로 다익스트라를 시작할 때 최소값을 구할 수 있는지 알아내야합니다.

 

테스트케이스 예

4, [[0, 1, 5], [0, 2, 3], [1, 2, 1], [1, 3, 2], [2, 3, 4]] : 6

시작점이 0일 땐 6이나오고, 시작점이 1일땐 8이 나옵니다. 이러한 이유 때문에 0번부터 n까지 시작점을 모두 넣어봐야합니다.

 

#include <string>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

vector<pair<int, int > > graph[101];
int dist[101];
bool visit[101];

void D(int node) {
    priority_queue<pair<int, int >, vector<pair<int, int > >, greater<pair<int, int > > > pq;
    pq.push({ 0, node });
    dist[node] = 0;
    
    while(!pq.empty()) {
        auto now = pq.top();
        int v = now.second;
        int e = now.first;
        pq.pop();
        
        // if(visit[v]) continue;
        visit[v] = true; // 각 노드를 한번만 방문한다.
        
        for(auto g : graph[v]) {
            int next = g.first;
            int nextVal = g.second; // 누적 가중치가 아닌, 두 노드사이의 가중치
            if(!visit[next] && dist[next] > nextVal) {
                dist[next] = nextVal;
                pq.push({ nextVal, next });
            }
        }
    }
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 2147000000;
    
    for(auto c : costs) { // 양방향 인접 그래프 만들기
        graph[c[0]].push_back({ c[1], c[2] });
        graph[c[1]].push_back({ c[0], c[2] });
    }
    
    for(int i = 0; i < n; i++) { // 시작점을 바꿔가며 각 노드의 최단 경로를 구한다.
        for(int j = 0; j < n; j++) {
            dist[j] = 2147000000;
        }
        
        D(i);
        
        int tmp = 0;
        for(int j = 0; j < n; j++) { // 해당 시작점에서의 최단 경로 합을 구한다.
            if(visit[j]) tmp += dist[j];
        }
        
        answer = min(answer, tmp); // 최소값 갱신
        memset(visit, false, sizeof(visit)); // 초기화
    }
    
    return answer;
}