알고리즘 :: 이것이 코딩 테스트다 :: 최단거리 :: Q40 :: 숨바꼭질

문제

동빈이는 1번 헛간으로부터 최단 거리가 가장 먼 헛간에 숨는다. 동빈이가 숨을 헛간의 번호를 출력하는 프로그램을 잣성하세요.

문제접근

• 동빈이는 항상 1번 헛간으로부터 시작하므로 시작점이 정해져있고 다른 모든 정점까지의 거리를 구한 뒤 문제 조건에 맞는 정답을 구하는 전형적인 다익스트라 알고리즘 문제다.

코드

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

static int N, M, dist[20001];
static vector<int> place[20001];

void dijkstra() {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({1, 0});	// 시작지점과 거리를 넣어준다.
    dist[1] = 0;	// 시작지점의 거리를 초기화한다.

    while(!pq.empty()) {
        int curVertex = pq.top().first, cost = pq.top().second;
        pq.pop();
		// 기록된 최소 거리보다 cost가 크다면 갱신 불필요함.
        if (dist[curVertex] < cost) continue;
        for (const int& itr : place[curVertex])
            if (dist[itr] > cost + 1) {
                dist[itr] = cost + 1;
                pq.push({itr, cost + 1});
            }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int s, e;   cin >> s >> e;
        place[s].push_back(e);
        place[e].push_back(s);
    }
    fill(dist + 1, dist + N + 1, 1e9);
    dijkstra();
    
    // 최종적으로 답을 구하는 과정
    auto itr = max_element(dist + 1, dist + N + 1);
    int answerDist = *itr, hidePlace = itr - dist;
    int dupCount = 0;
	for (int i = 1; i <= N; ++i)
		if (place[i] == answerDist) dupCount++;
    cout << hidePlace << ' ' << answerDist << ' ' << dupCount << '\n';
}

• 다익스트라 알고리즘을 구현하는 과정까지는 공식이라 너무 쉽다.
• 최종적으로 답을 구하는 과정은 다음과 같다.
  • max_element() 함수는 컨테이너에서 최대값을 찾은 뒤 해당 지점의 iterator를 반환한다.
  • 따라서 가장 먼 거리 answerDIst는 반환된 반복자의 포인터다.
  • 숨는 장소 hidePlace, 반복자의 인덱스 번호를 알기 위해서는 begin()에서 빼준다.

예시 입력

6 7
3 6
4 3
3 2
1 3
1 2
2 4
5 2

4 2 3