[BOJ/Gold 2] 백준 31502 만화에서 나오는 거 따라하고 그러면 안 된다(C++)

문제 링크

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

 

 

문제

토카는 어쩌다 마주친 아름다운 한별 선배에게 마음을 빼앗겨 버리고 말았다! 말을 걸고 싶었지만 그럴 자신이 없었던 토카는 한별 선배에게 말을 걸 만한 명분을 찾기 시작했다. 평소에 만화를 많이 읽던 토카는 그 명분을 만들 방법을 한 만화책에서 찾아냈다! 만화 속 남자 주인공과 여자 주인공이 등굣길에 벚꽃 아래에서 서로 부딪혔던 사건을 계기로 친해졌다는 내용을 보고 직접 따라 하기로 결심했다.

토카네 동네에는 벚나무가 없기 때문에 대신 은행나무가 있는 곳에서 시도하고자 한다. 토카네 동네는 1부터 N까지의 번호가 붙은 N개의 은행나무와 양 끝에 은행나무가 심어진 M개의 도로로 구성되어 있다. 모든 도로는 양방향 이동이 가능하며, 임의의 두 은행나무 사이를 항상 이동할 수 있다. 서로 다른 두 은행나무를 잇는 도로가 둘 이상일 수도 있다.

토카는 한별 선배 집 앞 은행나무의 번호와 등교하는 방법에 대해서 알아냈다. 한별 선배는 탁 트인 곳을 좋아해서 한 은행나무에서 인접한 다른 은행나무로 갈 때 연결된 도로가 가장 많은 은행나무로, 만약 그러한 은행나무가 여러 그루 있으면 가장 큰 번호를 가진 은행나무로 이동한다. 하지만 도로가 많은 길만 따라가다 보면 같은 도로만 빙빙 돌 수 있기 때문에 학교로 가는데 거치는 은행나무 수가 가장 적은 경로로 이동한다. 따라서 더 많은 도로가 연결된 은행나무라 하더라도 거치는 은행나무 수를 최소화할 수 없다면 그쪽으로는 향하지 않는다.

토카는 한별 선배와 같이 있는 시간을 길게 만들기 위해서 한별 선배가 등굣길에 지나치는 은행나무 중 토카네 집에서 가장 빨리 도착할 수 있는 은행나무에서, 만일 그런 은행나무가 여러 그루라면 번호가 가장 작은 은행나무 앞에서 부딪힌다는 계획을 세웠다. 김칫국을 마시고 있는 토카를 대신해 당신이 토카와 한별 선배가 부딪힐 운명의 은행나무를 알려 줘야 한다!

 

입력

첫 번째 줄에는 은행나무의 개수를 나타내는 N(3 ≤ N ≤ 100,000)과 도로의 개수를 나타내는 M(2 ≤ M ≤ 300,000)이 공백으로 구분되어 주어진다.

두 번째 줄에는 토카의 집과 인접한 은행나무 번호 A와 한별 선배의 집과 인접한 은행나무 번호 B와 학교와 인접한 은행나무 번호 C가 공백으로 구분되어 주어진다. (1 ≤ A, B, C ≤ N; A ≠ B; A ≠ C; B ≠ C)

마지막으로 세 번째 줄부터 M개의 줄에 걸쳐 도로 양 끝에 심겨 있는 은행나무 번호 i, j (1 ≤ i, j ≤ N; i ≠ j)와 도로를 이동하는 데 걸리는 시간 k (1 ≤ k ≤ 10^9)이 공백으로 구분되어 주어진다.

 

출력

토카가 가야 할 운명의 은행나무 번호를 출력한다.

 

예제 입력 1

10 12
5 1 10
1 3 6
1 4 11
2 3 7
3 6 3
3 7 8
4 5 3
4 7 5
7 8 17
7 9 6
2 5 3
10 9 13
10 8 21

예제 출력 1

7

 

알고리즘 분류

• 그래프 탐색
• 최단 거리 알고리즘

 

풀이

먼저 한별 선배의 B번 나무부터 C번 나무까지의 경로를 추적해야, 토카의 시점에서 데이크스트라를 수행하고 운명의 은행나무를 고를 수 있다.

엄청나게 틀린 문제인데, 문제를 제대로 이해했으나 한별 선배의 경로를 구하는 방법이 잘못되었다.

B번 나무에서 시작해서 C번 나무까지 BFS를 수행하며, 각 나무마다 몇 번째로 방문하는지를 기록하고 C번 나무에서 거꾸로 B번 나무까지 가면서 한별 선배의 경로로써 올바른 나무를 골랐다.

그런데, 이렇게 하면 B번 나무에서 경로로써 선택한 나무로 이동할 때, 해당 나무가 최적의 나무인지를 보장할 수가 없다. B번 나무에서 출발할 때의 최적의 나무만 골라서 C번 나무에 도달하는 경우와 C번 나무에서 출발할 때의 최적의 나무만 골라서 B번 나무에 도달하는 경우가 다르다.

C번 나무에서 출발할 때의 최적의 나무를 골랐으나, 이것이 B번 나무에서 출발할 때의 최적의 나무가 아닐 수도 있다는 것이다.

따라서 반대로, C번 나무에서 출발하는 BFS를 수행한다. 그리고 B번 나무에서 출발해서 C번 나무까지 도달할 때의 경로에 포함될 최적의 나무를 구한다.

그 이후에는 간단하다. 토카의 시점에서 데이크스트라를 수행한다. A번 나무에서 N - 1 그루의 나무까지 도달하는 데 필요한 최소 시간을 기록한다.

마지막으로, 한별 선배의 경로에 포함되는 나무들 중, A번 나무에서 해당 나무까지 이동할 때 걸리는 시간 중 가장 짧은 시간을 가지는 나무를, 그런 나무가 여러 그루면 번호가 가장 낮은 나무를 운명의 은행나무로써 선택한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 100001
#define INF_LL 4e14
#define INF_INT 1e9
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, A, B, C, I, J;
LL K;
vector<pair<int, LL> > Edges[MAX];
bool isPath[MAX];
int Visited[MAX];
LL Dist[MAX];
int Answer;

void init() {
    for (int i = 0; i < MAX; i++) {
        Visited[i] = INF_INT;
        Dist[i] = INF_LL;
    }
}

void input() {
    cin >> N >> M;
    cin >> A >> B >> C;
    for (int i = 0; i < M; i++) {
        cin >> I >> J >> K;
        Edges[I].push_back(make_pair(J, K));
        Edges[J].push_back(make_pair(I, K));
    }
}

void bfsHanbyeol() {
	queue<pair<int, int> > Q;
	Visited[C] = 0;
	Q.push(make_pair(C, 0));

	while (!Q.empty()) {
		int NowT = Q.front().first;
		int NowC = Q.front().second;
		Q.pop();

		for (int i = 0; i < (int)Edges[NowT].size(); i++) {
			int NextT = Edges[NowT][i].first;
			if (Visited[NextT] > NowC + 1) {
				Visited[NextT] = NowC + 1;
				Q.push(make_pair(NextT, NowC + 1));
			}
		}
	};
}

void findHanbyeolPath() {
	int NowT = B;

	while (true) {
		isPath[NowT] = true;
		if (NowT == C) break;

		int NextT = -1;
		int NextTRoadCount = -1;

		for (int i = 0; i < (int)Edges[NowT].size(); i++) {
			int Next = Edges[NowT][i].first;
			if (Visited[Next] != Visited[NowT] - 1) continue;

			int RoadCount = (int)Edges[Next].size();
			if (NextTRoadCount < RoadCount) {
				NextTRoadCount = RoadCount;
				NextT = Next;
			}
			else if (NextTRoadCount == RoadCount) {
				NextT = max(NextT, Next);
			}
		}

		NowT = NextT;
	};
}

void dijkstraToka() {
    priority_queue<pair<LL, int> > PQ;
    PQ.push(make_pair(0, A));
    Dist[A] = 0;

    while (!PQ.empty()) {
        LL NowT = -PQ.top().first;
        int NowX = PQ.top().second;
        PQ.pop();

        if (Dist[NowX] < NowT) {
            continue;
        }

        for (int i = 0; i < (int)Edges[NowX].size(); i++) {
            LL NextT = Edges[NowX][i].second;
            int NextX = Edges[NowX][i].first;
            if (Dist[NextX] > Dist[NowX] + NextT) {
                Dist[NextX] = Dist[NowX] + NextT;
                PQ.push(make_pair(-Dist[NextX], NextX));
            }
        }
    };
}

void findTokaTree() {
	LL MinDist = INF_LL;

	for (int i = 1; i <= N; i++) {
		if (!isPath[i]) continue;
		LL NowDist = Dist[i];
		if (MinDist > NowDist) {
			MinDist = NowDist;
			Answer = i;
		}
		else if (MinDist == NowDist) {
			Answer = min(Answer, i);
		}
	}
}

void settings() {
    bfsHanbyeol();
	findHanbyeolPath();
    dijkstraToka();
	findTokaTree();
}

void printAnswer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO

    init();
    input();
    settings();
    printAnswer();

    return 0;
}