[BOJ-1238] 파티(C++)

백준 1238 파티

 

1238번: 파티

 

문제 설명

 

 - N개의 숫자로 구분된 마을에 한 명의 학생이 살고 있다.

 

 - N명의 학생은 X번 마을에 모여 파티를 벌인다.

 

 - 마을에는 총 M개의 단방향 도로가 존재하고, 이 도로를 지나는데 Ti의 시간이 걸린다.

 

 - 각 마을의 학생들은 파티에 참석하기 위해 걸어가고, 다시 그들의 마을로 돌아온다.

 

 - 학생들은 최단 시간에 오고 가기를 원한다.

 

 - 모든 학생들은 집에서 X에 갈 수 있고, 집으로 돌아올 수 있다.

 

 - N명의 학생들 중 오고 가는데 가장 많은 시간을 소비한 학생의 소요시간을 출력하라.

 

---

 

입력 값

 

 - 첫째 줄에 N( 1 <= N <= 1,000 ), M ( 1<= M <= 10,000), X ( 1<= X <= N) 가 공백으로 구분되어 입력된다.

 

 - 둘째 줄부터 M+1 번째 줄 까지 i번째 도로의 시작점, 끝점, 소요시간이 들어온다.

 

 - 시작점과 끝점이 같은 도로는 없고, 도시 A에서 도시 B로 가는 도로의 개수는 최대 1개이다.

 

---

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 모든 마을에서 X번 마을로 가는 최단 경로와 X번 마을에서 모든 마을로 가는 최단 경로를 구하고,

   그 값의 합이 가장 작은 마을을 구하면 된다.

 

 - 즉, (i번째 마을 -> X번 마을로 가는 최단 경로) + (X번 마을 -> i번째 마을로 가는 최단 경로) 가 최대가 되는 값을 구하면 된다.

 

 - 단순히 생각하면, 플로이드-워셜 알고리즘을 이용하며 모든 마을의 최단 경로를 경로를 구한 후 더하면 된다고 판단할 수 있다. 

최단 경로 알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘

 

 - 하지만, 플로이드-워셜 알고리즘은 시간 복잡도가 O($N^3$)이다.

   즉 , 이 경우에는 최대 $1000^3$ = 10억이 되기 때문에 시간초과가 발생한다.

 

 

 - 결국, 이 문제에는 플로이드-워셜이 아니라, 다익스트라를 사용해야 한다.

최단 경로 탐색 알고리즘 - 다익스트라(Dijkstra)

 

 - 다익스트라는 특정 노드에서 모든 노드로 가는 최단 경로를 의미한다.

   즉, 노드 X에서 다른 마을로 가는 최단 경로는 쉽게 구할 수 있다.

 

 - 그렇다면, 다른 모든 노드에서 노드 X로 가는 최단 경로는 어떻게 구할 수 있을까?

   그 방법은 주어진 경로를 뒤집은 후 노드 X에서 다른 마을로 가는 최단 경로를 구하면 된다.

 

 

 

 

 

 

 - 위 그림을 살펴보면, 다른 노드에서 노드1로 가는 최단 경로와

   경로를 뒤집은 후 노드 1에서 다른 노드로 가는 최단 경로가 같은 것을 알 수 있다.

---

 

 

소스 코드

 

#include <bits/stdc++.h>

using namespace std;

int N, M, X;

// 정상 경로 : X에서 다른 노드 가는 최단 경로 계산용 
vector<pair<int,int>> road[1001];

// 뒤집은 경로 : 다른 노트에서 X로 가는 최단 경로 계산용
vector<pair<int, int>> roadReverse[1001];

// 정상 경로에서 사용하는 최단 경로 계산
int visited[1001];

// 뒤집은 경로에서 사용하는 최단 경로 계산
int visitedReverse[1001];


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

	fill_n(visited, 1001, INT_MAX);
	fill_n(visitedReverse, 1001, INT_MAX);

	cin >> N >> M >> X;

	for (int i = 0; i < M; i++) {

		int s, e, t;
		cin >> s >> e >> t;
		road[s].push_back({ e,t });
		roadReverse[e].push_back({ s,t });

	}

	// 정상 경로 다익스트라
	visited[X] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push({ 0,X });

	while (!pq.empty()) {
		
		int nowNode = pq.top().second;
		int nowCost = -pq.top().first;
		pq.pop();

		for (auto next : road[nowNode]) {

			int nextNode = next.first;
			int nextCost = next.second;

			if (visited[nextNode] > nowCost + nextCost) {
				visited[nextNode] = nowCost + nextCost;
				pq.push({ -visited[nextNode],nextNode });
			}

		}

	}

	// 뒤집은 경로 다익스트라
	visitedReverse[X] = 0;
	pq.push({ 0,X });

	while (!pq.empty()) {

		int nowNode = pq.top().second;
		int nowCost = -pq.top().first;
		pq.pop();


		for (auto next : roadReverse[nowNode]) {

			int nextNode = next.first;
			int nextCost = next.second;

			if (visitedReverse[nextNode] > nowCost + nextCost) {
				visitedReverse[nextNode] = nowCost + nextCost;
				pq.push({ -visitedReverse[nextNode],nextNode });
			}

		}

	}

	// 최단경로가 가장 큰 경로 찾기
	int result = 0;
	for (int i = 1; i <= N; i++) {
		int sum = visited[i] + visitedReverse[i];
		result = max(result, sum);
	}

	cout << result << endl;


	return 0;
}