[백준] 6118번 숨바꼭질

[적용한 알고리즘]

다익스트라

 

[아이디어]

내용

 

[생각의 흐름 / 절차] 

내용

 

[교훈]

잠이 안와서 푸는 기본문항

 

<코드>

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

const int MAX_V = 20001;
const int INF = 1000000000;
typedef pair<int, int> P;

int main(){
    int V, E;
    vector<P> adj[MAX_V];
    scanf("%d %d", &V, &E);

    for (int i = 0; i < E; i++){
        int from, to;
        scanf("%d %d", &from, &to);
        adj[from].push_back(P(to, 1));
        adj[to].push_back(P(from, 1));
    }

    int dist[MAX_V];
    fill(dist, dist + MAX_V, INF);
    bool visited[MAX_V] = { 0 };
    priority_queue<P, vector<P>, greater<P>> PQ;

    dist[1] = 0;
    PQ.push(P(0, 1));

    while (!PQ.empty()){
        int cur;
        do {
            cur = PQ.top().second;
            PQ.pop();
        } while (!PQ.empty() && visited[cur]);

        if (visited[cur]) break;

        visited[cur] = true;
        for (auto &p : adj[cur]){
            int nxt_node = p.first;
            int nxt_cost = p.second;

            if (dist[nxt_node] > dist[cur] + nxt_cost){
                dist[nxt_node] = dist[cur] + nxt_cost;
                PQ.push(P(dist[nxt_node], nxt_node));
            }
        }
    }

    int ans_dist = -1;
    int ans_idx;
    int ans_cnt = 0;

    for (int i = V; i >= 1; i--){
        if (ans_dist < dist[i] && dist[i] != INF){
            ans_dist = dist[i];
            ans_idx = i;
            ans_cnt = 1;
        }
        else if (ans_dist == dist[i]){
            ans_idx = i;
            ans_cnt++;
        }
    }
    printf("%d %d %d\n", ans_idx, ans_dist, ans_cnt);

    return 0;
}