[백준] 22865번 가장 먼 곳 (C++)

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

 

 

이 문제는 친구 3명이 거주중인 노드가 주어지고 거주지마다 얼마나 걸리는지 그래프 관계가 주어졌을때

3명의 거주지를 제외한 가장 먼 노드를 출력하는 문제이다.

 

그렇다면 생각해볼 수 있는것이 노드의 최대 개수가 10만이고 친구의 개수는 3개가 고정이기 때문에

친구의 노드를 이용하여 모든 노드의 거리를 계산할 수 있기때문에

 

친구 노드 3개를 다익스트라 알고리즘을 사용하여 계산하여 테이블 형식으로 만들었다.

 

 

따라서 hashmap을 사용하여 테이블 형식으로 만들어 가장 큰값을 갱신하여 출력해주었다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    string s;
    vector<int> v;
};

int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
int N, M, result;
vector<vector<pii>> v(100001);
int dist[100001];
vector<int> locate;
map<int, vector<int>> m;
set<int> st;
int gaps;

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

    while(!pq.empty()) {
        int Node = pq.top().second;
        int Cost = pq.top().first;
        pq.pop();

        if(dist[Node] < Cost) continue;

        for(auto it : v[Node]) {
            int NextNode = it.first;
            int NextCost = Cost + it.second;

            if(dist[NextNode] > NextCost) {
                pq.push({NextCost, NextNode});
                dist[NextNode] = NextCost;
            }
        }
    }
    for(int i = 1; i <= N; i++) {       // key
        if(st.count(i) > 0) continue;
        m[i].push_back(dist[i]);
    }
}

void Init() {
    for(int i = 1; i <= N; i++) {
        dist[i] = MAX;
    }
}

void solve() {
    for(auto it : locate) {
        Init();
        dijkstra(it);
    }

    for(auto it : m) {				// 최댓값을 찾아서 갱신
        int x = it.first;
        vector<int> tmp = it.second;
        int gap = MAX;

        for(auto iter : tmp) {
            if(gap > iter) {
                gap = iter;
            }
        }
        if(gaps < gap) {
            result = x;
            gaps = gap;
        }
    }

    cout << result;
}

void input() {
    cin >> N;

    for(int i = 0; i < 3; i++) {
        int a;
        cin >> a;
        locate.push_back(a);
        st.insert(a);
    }

    cin >> M;

    for(int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

 

회고록

처음엔 무턱대고 N개의 노드중 3개를 제외하여 다익스트라를 사용했는데 무조건 시간초과가 날 수밖에 없는 구조였다.

곰곰히 생각해보니 친구의 개수는 고정이기 때문에 시간초과를 피해갈 수 있는 구조로 설계하였다.

나중에 스터디 사람들과 같이 얘기해보니 다익스트라 함수를 한번만 사용하여 그중 가장 먼 노드를 출력하는 방법도 있었다.

이 방법은 3개의 노드를 0으로 갱신한 후 미리 힙에 3개를 넣고 호출하면 그에 따라서 가장 먼 노드가 출력이 된다.