[백준] 1238 - 파티 by C++

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

1238번: 파티

관점 뒤집기라고해야하나?

개인적으로 참신한 관점에서의 풀이를 발견해서 이를 남기려한다.

 

 

알고리즘 방식

핵심은

1. X 에서 모든 정점까지의 거리 ( vector<int> value; )

2. 모든 정점에서 X 까지의 거리 ( vector<int> reverseValue; )

위 값을 구하고, 이를 바탕으로 정답을 도출한다.

 

일반적인 풀이로는

모든 정점에 대해서 다른 정점까지의 거리를 구한 후, 이를 바탕으로 정답을 도출한다. (시간복잡도 NMlogN; VElogV)

반면에 위의 경우, 시간복잡도가 2NMlogN(; 2ElogV)으로 훨씬 간단하다.

 

방법으로는 앞선 1. X에서 모든 정점까지의 거리 를 일반적인 다익스트라 알고리즘을 통해 구한다.

 

다음으로 2. 모든 정점에서 X까지의 거리 를 구해야하는데, 이를 다른 관점에서 바라봐야한다.

 

from 에서 to 로 가는 비용을 cost 라고하자.

X 에서 a 로 가는 비용이 c 라면

a 에 X 부터 오는 비용이 c 이다. 

같은 말이지만 관점이 뒤집혔다. 이는 코드의 [25, 26] 에 반영되어 있다.

node[from].push_back({cost, to});
reverseNode[to].push_back({ cost, from });

다시 정리하자면, 일반적으로 다익스트라 알고리즘의 경우, X 에서 모든 정점까지의 거리 를 구하는 알고리즘이다. 그리고 이를 위해 25번째 줄과 같이 a 에서 b로 가는 간선의 비용을 저장해주고 알고리즘을 실행한다.

다시, 모든 정점에서 X까지의 거리를 구하기 위해서는 26번째 줄과 같이 b을 a로부터 가는 간선의 비용을 저장해주고 알고리즘을 실행하면 된다.

 

말 장난 같기도 한데.... 내 머리로는 이 이상 설명을 못하겠다.

후자와 같이 바꿨을 때, 알고리즘이 내부적으로 어떻게 동작해서 결과가 나오는지 직접 확인해보면 아마 이해가될 것이다.

 

 

이런 식으로 생각하는 방법도 있다.

구현한 다익스트라 프로그램을 속인다 생각해보자.

( 결과인 A에서 모든 정점까지의 거리라는 배열에 집중하자.)

 

프로그램은 화살표의 방향을 알지못하고, 입력해준 방식을 통해 화살표의 방향을 인지한다.

A에서 B로 가는 거리는 E1

A에서 C로 가는 거리는 E2

C에서 B로 가는 거리는 E3

라고 프로그램에게 알려준다면,

앞 쪽 그림이라고 생각하고 이에 대한 결과인 A에서 모든 정점까지의 거리 배열을 반환한다.

 

이번에는 프로그램에게 거짓말을 해보자.

B에서 A로 가는 거리는 E1

C에서 A로 가는 거리는 E2

B에서 C로 가는 거리는 E3

라고 프로그램에게 알려주고 결과를 도출하면 어떻게 될까?

우리가 준 정보에 대해 앞 쪽 그림이라고 생각하고 다시 A에서 모든 정점까지의 거리 배열을 반환할 것이다.

하지만, 우리는 거짓말을 했고, 사실 프로그램은 뒤 쪽 그림에 대한 결과를 반환했다.

다시 결과에 집중해보자.

화살표의 방향이 반대로 뒤집힌다면, 결과는 무엇을 의미할까?

그렇다. 모든 정점에서 A로 가는 거리의 배열이 된다. 

 

 

우리는 거짓말을 했으므로, 화살표의 방향을 원래대로 뒤집으면

모든 정점에서 A까지의 거리가 구해져 있음을 알 수 있다.

 

 

소스 코드

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

int N, M, X;
vector<vector<pair<int, int>>> node;
vector<vector<pair<int, int>>> reverseNode;
vector<int> value;
vector<int> reverseValue;

void input() {
	cin >> N >> M >> X;

	node.resize(N + 1, vector<pair<int, int>>());
	reverseNode.resize(N + 1, vector<pair<int, int>>());
	value.resize(N + 1, INT_MAX);
	reverseValue.resize(N + 1, INT_MAX);

	for (int i = 0; i < M; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		node[from].push_back({cost, to});
		reverseNode[to].push_back({ cost, from });
	}
}

void daijkstra(vector<vector<pair<int, int>>> &n, vector<int> &v) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
	pq.push({ 0, X });
	v[X] = 0;
	while (!pq.empty()) {
		int cost = pq.top().first;
		int vertex = pq.top().second;
		pq.pop();

		for (int i = 0; i < n[vertex].size(); i++) {
			int nCost = n[vertex][i].first;
			int nxtVertex = n[vertex][i].second;

			if (v[nxtVertex] > cost + nCost) {
				v[nxtVertex] = cost + nCost;
				pq.push({ v[nxtVertex], nxtVertex });
			}
		}
	}
}

int solution() {
	daijkstra(node, value);
	daijkstra(reverseNode, reverseValue);

	int ans = 0;
	for (int i = 1; i <= N; i++) {
		if (ans < value[i] + reverseValue[i])
			ans = value[i] + reverseValue[i];
	}
	return ans;
}

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

	input();

	cout << solution();
}