[ 백준 13424 ] 비밀 모임 (C++) - Dijkstra

---

🔗 문제 링크

13424번: 비밀 모임

---

💡 문제 풀이 및 해석

1. N의 범위가 100 이하이므로, 1N번 방에서 1N번 방까지 가는 최소값 거리를 모두 구해도 1초안에 해결되는 문제다.
2. 모든 방에서 모든 방까지 가는 최소의 거리를 다익스트라를 통해서 구한다.
3. 이 최솟값들을 모든 방에 더해준다.
4. 가장 값이 작은 방이 모이기 최적화된 방이다.
5. 값이 같은 경우, 번호가 낮은 수가 출력되어야 한다.

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define INF 987654321
using namespace std;

int T, N, M, K;
int moveCost[101]; // 100개의 방에 가는 최솟값 비용
int roomCost[101]; // 방에 오는 코스트
vector<pair<int,int>> road[101]; // start , {end ,cost};
vector<int> inK;

void init() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int start, end, cost;
        cin >> start >> end >> cost;
        road[start].push_back({ end,cost });
        road[end].push_back({ start,cost });
    }
    cin >> K;
    for (int i = 0; i < K; i++) {
        int num; cin >> num;
        inK.push_back(num);
    }
}

void dik(int start) {

    moveCost[start] = 0;
    queue<int> q;
    q.push(start);

    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (int i = 0; i < road[cur].size(); i++) {
            int next = road[cur][i].first;
            int cost = road[cur][i].second;
            int nextCost = moveCost[cur] + cost;
            if (moveCost[next] > nextCost) {
                moveCost[next] = nextCost;
                q.push(next);
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        roomCost[i] += moveCost[i];
    }
}

void sol() {
    for (int i = 1; i <= N; i++) {
        roomCost[i] = 0; // 테스트 케이스마다 roomCost는 초기화 시켜줘야함.
    }
    for (int i = 0; i < inK.size(); i++) {
        for (int i = 1; i <= N; i++) {
            moveCost[i] = INF; // 각각의 방에서 탐색이 끝나면 매번 초기화 시켜줘야함.
        }
        int start = inK[i];
        dik(start);
    }
}

int main() {

    cin >> T;

    while (T--) {
        init();
        sol();
        int answerCost = INF;
        int answerNum;
        // 낮은 방번호부터 검사하므로 방까지 가는 거리가 같으면 번호가 낮은 방이 출력된다.
        for (int i = 1; i <= N; i++) { 
            if (answerCost > roomCost[i]) {
                answerNum = i;
                answerCost = roomCost[i];
            }
        }
        cout << answerNum << endl;
        // 테스트 케이스마다 전역변수 초기화
        inK.clear();
        for (int i = 1; i <= N; i++) {
            road[i].clear();
        }
    }

    return 0;
}

---

🤔 문제 후기

구현에 다익스트라 문제였는데, 문제를 보자마자 다익스트라로 풀어야 겠다고 생각했다. 처음에는 road.clear()로 초기화가 될 것이라고 생각했는데(자동으로 road->clear();로 바뀜), 초기화가 되지 않아서 틀린 이유를 몰랐다. 생각해보니 배열인데 포인터가 들어가는 것 자체가 말이 안되는 거였는데 말이다. 이 점을 제외하고는 문제가 특별히 어렵진 않았다.