[Baekjoon] 1238번 파티.cpp

[백준] 1238번 파티 문제 링크

· 메인 아이디어

다익스트라 응용 문제로, 한 쌍의 출발지와 목적지를 설정하고 구하는 문제가 아닌 모든 노드에 대해 특정 노드를 거쳤다가 돌아오는 경로를 구하는 문제이다.

일반적으로 다익스트라 문제는 특정 노드에서 출발하여 갈 수 있는 모든 노드들에 대한 거리를 전부 구한다. 따라서 이번 문제는 각 노드에서 경유지까지의 최단 경로를 각각 구하고, 경유지부터 모든 노드까지의 최단 경로를 구하여 $n+1$ 번의 다익스트라 알고리즘을 실행해주면 될 것이다.

우선순위 큐를 이용한 다익스트라 알고리즘은 약 $mlogn$이므로 n = 1000, m = 10000일 때 $n+1$번의 다익스트라 알고리즘 연산 수는 약 $1000 * 10000 * log 1000$ 회로 추정할 할 수 있고, 아슬아슬하게 시간제한 1초 안에 해결될 것으로 보인다.

그렇게 해결한 결과, 예상대로 문제가 해결되었다.

하지만 문제를 해결한 다른 사람들의 알고리즘은 $0ms$의 실행 시간을 보였고, 일반적으로 사용하는 입출력 방식의 개선 정도의 차이가 아니었다. 그들의 코드를 살펴본 결과, 다익스트라 알고리즘을 단 두 번만 실행한 것을 확인할 수 있었다.

· 개선 방법

한 번의 다익스트라로 각 노드에서 경유 노드까지의 거리를 구했다는 것인데, 고민하다가 문득 경로를 뒤집으면 되겠다는 생각이 들었다. 예를 들어,

이런 경로를

이렇게 뒤집고, 가중치를 똑같이 설정해도, 출발점과 도착점만 뒤바뀔 뿐 그 최단거리는 변하지 않는다. 따라서, 처음 그래프를 초기화할 때 정상적으로 간선 정보를 저장한 그래프 하나와, 출발점과 도착점을 반대로 저장하는 그래프를 따로 만들어 정보를 저장하였다.

그리고 각 그래프에 대해 경유 노드 x로 다익스트라 알고리즘을 실행한 결과,

예상대로 실행 시간이 대폭 개선된 것을 확인할 수 있었다. 아래는 개선된 코드 전문이다.

#include <iostream>
#include <queue>
#include <vector>
#define MAX_SIZE 1001
#define INF 1000000000

int n, m, x;
std::vector<std::pair<int, int>> goGraph[MAX_SIZE];
std::vector<std::pair<int, int>> backGraph[MAX_SIZE];

std::priority_queue<std::pair<int, int>> q;

int goDistance[MAX_SIZE];
int backDistance[MAX_SIZE];

void dijkstra(int startNode, std::vector<std::pair<int, int>>* graph, int* distance) {
	for (auto adj : graph[startNode]) {
		q.push({ -adj.first, adj.second });
		if (distance[adj.second] > adj.first) {
			distance[adj.second] = adj.first;
		}
	}

	while (!q.empty()) {
		int curNode = q.top().second;
		int curDistance = -q.top().first;
		q.pop();

		if (distance[curNode] >= curDistance) {
			for (auto adj : graph[curNode]) {
				if (distance[adj.second] > curDistance + adj.first) {
					distance[adj.second] = curDistance + adj.first;

					q.push({ -distance[adj.second], adj.second });
				}
			}
		}
	}
}

void init() {
	for (int index = 1; index <= n; index++) {
		goDistance[index] = INF;
		backDistance[index] = INF;
	}
}

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

	std::cin >> n >> m >> x;
	
	init();

	int node1, node2, weight;
	for (int count = 0; count < m; count++)
	{
		std::cin >> node1 >> node2 >> weight;
		goGraph[node2].push_back({ weight, node1 });
		backGraph[node1].push_back({ weight, node2 });
	}

	dijkstra(x, goGraph, goDistance);
	dijkstra(x, backGraph, backDistance);

	goDistance[x] = 0;
	backDistance[x] = 0;

	int max = 0;
	for (int index = 1; index <= n; index++) {
		if (max < goDistance[index] + backDistance[index]) {
			max = goDistance[index] + backDistance[index];
		}
	}

	std::cout << max;
}