[백준] 1238번 파티 C++ 풀이

---

알고리즘 분류

• 그래프 이론
• 최단 경로
• 다익스트라

---

문제 설명

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

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N) 번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

---

입력 설명

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈 수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

---

출력 설명

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

---

예제 입력

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

---

예제 출력

10

---

아이디어

기본적으로는 우선순위큐를 사용하는 다익스트라를 사용하지만 정석적인 방법으로 풀면

각 노드에서 모두 다익스트라를 진행해야 하기 때문에 시간이 너무 오래 걸린다.

그래서 그래프를 입력 받을 때 입력받은 그래프의 역방향 그래프도 함께 저장해서

x에서 순방향으로 한 번 역방향으로 한 번 다익스트라를 진행하면 모든 노드에서 x로 가는 최단 경로와

x에서 모든 노드로 가는 최단 경로를 다익스트라 2회 실행만으로 구할 수 있다.

---

알고리즘

3차원 벡터로 구성된 그래프를 G를 생성한다.

G[0]에는 순방향 그래프를 입력받고 G[1]에는 역방향 그래프를 입력받는다.

시작 노드에서 각 노드들까지의 거리를 나타내는 2차원 벡터 dist도 마찬가지로 

dist[0]은 순방향 dsit[1]은 역방향을 나타낸다. dist의 모든 값은 매우 큰 값으로 초기화한다.

이후 priority_queue를 선언한다.

일반적인 priority_queue는 top에 가장 큰 값이 들어있는 순서대로 자동 정렬되므로 이를 top에 가장 작은 값이

들어있도록 변경해 주기 위해서 priority_queue 생성 시 greater를 넣어준다.

벡터나 큐에 단일 값이 아닌 pair 형태로 넣기 때문에 pair의 first를 기준으로 정렬이 일어난다.

따라서 최소 시간을 기준으로 정렬하려면 벡터나 큐에 넣을 때 {소모 시간, 도착 노드} 순서로 넣어야 한다.

우선 시작하는 노드 x의 거리를 0으로 초기화시킨 후 priority_queue에 소모시간과 시작하는 노드를 넣어준다.

이후 priority_queue가 빌 때까지 while문을 돌린다.

while문 내부에서는 priority_queue의 top 즉, 현재 노드에서 갈 수 있는 노드 중 가장 짧은 시간이 소요되는 노드를 꺼낸다.

이후 꺼낸 노드에서 갈 수 있는 다른 노드들을 G에서 찾는다.

만약 기존의 dist보다 현재 노드를 거쳐서 가는 시간이 더 짧다면 현재 노드를 거쳐서 가도록 시간을 업데이트해 주고

해당 노드를 priority_queue에 넣어준다.

이와 같은 과정을 순방향으로 x에서 출발로 한 번 역방향으로 x에서 출발로 한 번 진행한 후

dist[0][i]+dist[1][i]의 값이 가장 큰 값을 출력한다.

---

코드

#include<iostream>
#include<vector>
#include<queue>
#include<climits>
using namespace std;
void dijk(vector<vector<vector<pair<int,int>>>> &G, vector<vector<int> > &dist, int k, int x)
{
	dist[k][x] = 0;
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
	pq.push({0,x});
	while(!pq.empty())
	{
		int cur = pq.top().second;
		int cost = pq.top().first;
		pq.pop();
		for(auto &next : G[k][cur])
		{
			int node = next.second;
			int ncost = next.first;
			if(dist[k][node] > cost + ncost )
			{
				dist[k][node] =  cost + ncost;
				pq.push({dist[k][node], node});
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m,x,max=0;
	cin>>n>>m>>x;
	vector<vector<vector<pair<int,int>>>> G(2,vector<vector<pair<int,int>>>(n+1,vector<pair<int,int>>()));
	vector<vector<int>> dist(2,vector<int>(n+1,INT_MAX));
	for(int i=0; i<m; i++)
	{
		int start,end,weight;
		cin>>start>>end>>weight;
		G[0][start].push_back({weight,end});
		G[1][end].push_back({weight,start});
	}
	dijk(G,dist,0,x);
	dijk(G,dist,1,x);
	for(int i=1; i<=n; i++) if(dist[0][i]+dist[1][i] > max) max = dist[0][i]+dist[1][i];
	cout<<max;
	return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/1238

처음에는 모든 정점에서 queue를 사용한 다익스트라를 사용해서 문제를 풀었다.

그 후 인터넷을 찾아보니 priority_queue를 사용하는 편이 더 빠르다고 해서

모든 정점에서  priority_queue를 사용한 다익스트라를 사용해서 문제를 풀었다.

그 후 인터넷을 찾아보니  priority_queue를 사용하는 다익스트라를 순방향과 역방향 2번만 사용하는 편이 더 빠르다고 해서 priority_queue를 사용하는다익스트라를 순방향과 역방향 2번만 사용해서 문제를 풀었다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!