백준 9694번무엇을 아느냐가 아니라 누구를 아느냐가 문제다 [C++]

https://www.acmicpc.net/problem/9694

 

 

#개요

 

다익스트라를 활용한 문제라는걸 쉽게 알아 볼 수 있는데

 

관건은 다익스트라로 알게된 최소비용 

    + 경로를 기억하는게 관건이다.

 

이 경로를 기억하는데서 좀 삽질을 했다.

 

#첫번째 코드 - 다익스트라/dfs가지치기

 

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>

using namespace std;

vector<vector<pair<int, int>>> nodes;
vector<int> dist;
vector<bool> visited;
vector<int> path;
vector<int> resultSeq;
int N, M;
int intimacy;
int minIntimacy;

void dijkstra(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({ 0, start });
    dist[start] = 0;

    while (!pq.empty()) {
        int curDist = pq.top().first;
        int curNode = pq.top().second;
        pq.pop();

        if (dist[curNode] < curDist) continue;

        for (auto edge : nodes[curNode]) {
            int nextNode = edge.first;
            int weight = edge.second;
            int sumWeight = curDist + weight;

            if (sumWeight < dist[nextNode]) {
                dist[nextNode] = sumWeight;
                pq.push({ sumWeight, nextNode });
            }
        }
    }
}

void dfs(int node) {
    if (node == M - 1) {
        if (intimacy < minIntimacy) {
            minIntimacy = intimacy;
            resultSeq = path; 
        }
        return;
    }

    visited[node] = true;
    for (auto a : nodes[node]) {
        int nextNode = a.first;
        int weight = a.second;
        if (!visited[nextNode] && intimacy + weight < minIntimacy) {  
            path.push_back(nextNode);
            intimacy += weight;
            dfs(nextNode);
            path.pop_back();
            intimacy -= weight;
        }
    }
    visited[node] = false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        cin >> N >> M;

        nodes.assign(M, vector<pair<int, int>>());
        dist.assign(M, INT_MAX);
        visited.assign(M, false);
        path.clear();
        resultSeq.clear();

        for (int i = 0; i < N; i++) {
            int x, y, z;
            cin >> x >> y >> z;
            nodes[x].push_back({ y, z });
            nodes[y].push_back({ x, z });
        }

        dijkstra(0); // Dijkstra로 각 노드까지의 최소 친밀도 계산

        intimacy = 0;
        minIntimacy = INT_MAX;
        path.push_back(0);
        visited[0] = true;  // 시작 노드 방문 표시

        dfs(0); // DFS로 최소 경로 탐색

        cout << "Case #" << t << ": ";
        if (!resultSeq.empty()) {
            for (int i : resultSeq) {
                cout << i << ' ';
            }
            cout << '\n';
        }
        else {
            cout << -1 << '\n';
        }
    }

    return 0;
}

 

우선 이 첫번째 코드는

다익스트라로 경로의 최소비용들을 알아낸 뒤에

void dijkstra(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({ 0, start });
    dist[start] = 0;

    while (!pq.empty()) {
        int curDist = pq.top().first;
        int curNode = pq.top().second;
        pq.pop();

        if (dist[curNode] < curDist) continue;

        for (auto edge : nodes[curNode]) {
            int nextNode = edge.first;
            int weight = edge.second;
            int sumWeight = curDist + weight;

            if (sumWeight < dist[nextNode]) {
                dist[nextNode] = sumWeight;
                pq.push({ sumWeight, nextNode });
            }
        }
    }
}

 

dfs 탐색을 이용해서 최소비용 경로를 찾아냈다.

 

void dfs(int node) {
    if (node == M - 1) {
        if (intimacy < minIntimacy) {
            minIntimacy = intimacy;
            resultSeq = path; 
        }
        return;
    }

    visited[node] = true;
    for (auto a : nodes[node]) {
        int nextNode = a.first;
        int weight = a.second;
        if (!visited[nextNode] && intimacy + weight < minIntimacy) {  
            path.push_back(nextNode);
            intimacy += weight;
            dfs(nextNode);
            path.pop_back();
            intimacy -= weight;
        }
    }
    visited[node] = false;
}

 

 

다만 여기서 잘 살펴보면 dfs 는 완전탐색시 

최대 M이 20이기 때문에 20! 이라서

시간초과가 난다 

때문에 가지치기를 사용해서

시간복잡도를 줄여줘야 정답을 맞을 수 있다.

 

if (!visited[nextNode] && intimacy + weight < minIntimacy) {  
            path.push_back(nextNode);
            intimacy += weight;
            dfs(nextNode);
            path.pop_back();
            intimacy -= weight;
        }

가지치기조건이 달려있는걸 확인 할 수 있다.

 

 

하지만 이렇게 복잡하게 풀 이유가 없다

다익스트라를 할때 경로만 기억해주면 되기 때문이다.

 

#두번째 코드 - 다익스트라 /경로기억

 

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        int N, M;
        cin >> N >> M;
        vector<vector<pair<int, int>>> adj(M);
        for (int i = 0; i < N; i++) {
            int x, y, z;
            cin >> x >> y >> z;
            adj[x].push_back({y, z});
            adj[y].push_back({x, z});
        }

        // 다익스트라 알고리즘
        vector<int> dist(M, INT_MAX);
        vector<int> prev(M, -1);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, 0}); // 시작점: 한신이
        dist[0] = 0;
        while (!pq.empty()) {
            int u = pq.top().second;
            int d = pq.top().first;
            pq.pop();
            if (d > dist[u]) continue;
            for (auto& edge : adj[u]) {
                int v = edge.first;
                int weight = edge.second;
                if (dist[v] > dist[u] + weight) {
                    dist[v] = dist[u] + weight;
                    prev[v] = u;
                    pq.push({dist[v], v});
                }
            }
        }

        // 결과 출력
        cout << "Case #" << t << ": ";
        if (dist[M-1] == INT_MAX) {
            cout << "-1\n";
        } else {
            vector<int> path;
            for (int cur = M-1; cur != -1; cur = prev[cur]) {
                path.push_back(cur);
            }
            reverse(path.begin(), path.end());
            for (int node : path) {
                cout << node << " ";
            }
            cout << "\n";
        }
    }
    return 0;
}

 

훨씬 코드가 짧아지고 신뢰성이 올라갔다

 

물론 dfs 만 사용해서 가지치기만 하더라도 답을 얻을 수 있다.

 

#세번째 코드 - dfs 가지치기

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

vector<vector<pair<int, int>>> adj;
vector<bool> visited;
vector<int> path;
vector<int> bestPath;
int N, M;
int bestCost = INT_MAX;

void dfs(int node, int cost) {
    if (cost >= bestCost) return;  // 가지치기: 이미 최소 비용보다 크면 중단
    if (node == M - 1) {  // 최고의원에 도달한 경우
        bestCost = cost;
        bestPath = path;
        return;
    }

    visited[node] = true;
    for (auto& edge : adj[node]) {
        int next = edge.first;
        int weight = edge.second;
        if (!visited[next]) {
            path.push_back(next);
            dfs(next, cost + weight);
            path.pop_back();
        }
    }
    visited[node] = false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        cin >> N >> M;
        adj.assign(M, vector<pair<int, int>>());
        visited.assign(M, false);
        for (int i = 0; i < N; i++) {
            int x, y, z;
            cin >> x >> y >> z;
            adj[x].push_back({y, z});
            adj[y].push_back({x, z});
        }

        bestCost = INT_MAX;
        path.clear();
        bestPath.clear();
        path.push_back(0);

        dfs(0, 0);

        cout << "Case #" << t << ": ";
        if (bestCost == INT_MAX) {
            cout << "-1\n";
        } else {
            for (int i : bestPath) {
                cout << i << " ";
            }
            cout << "\n";
        }
    }
    return 0;
}

 

 

#결론

 

dfs를 이용한 가지치기는

시간복잡도를 확실하기 계산하기 어렵기 때문에

다익스트라로 경로만 기억하는 풀이가 제일 좋다고 할 수 있다.