(C++) 백준 1238 : 파티 (다익스트라)

문제

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명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

 

예제 입력 1 

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

예제 출력 1 

10

 

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

1238번: 파티

 

---

 

나의 풀이(수정 전):

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int NOT = 999999;

int N, M, X;
vector<vector<pair<int, int>>>map; 
vector<vector<int>>result; 

void dijkstra(int start)
{
	result[start][start] = 0;
	priority_queue<pair<int, int>>pq;
	pq.push({ start,0 });
	while (!pq.empty())
	{
		int now = pq.top().first; 
		int dist = -pq.top().second; 
		pq.pop();
		if (result[start][now] < dist) continue;
		for (int i = 0; i < map[now].size(); i++)
		{
			int next = map[now][i].first;
			int a = dist + map[now][i].second;
			int b = result[start][next];
			if (a < b)
			{
				result[start][next] = a;
				pq.push({ next, -a });
			}
		}
	}
}

int main()
{
	cin >> N >> M >> X; 
	X--;
	result.assign(N, vector<int>(N, NOT));
	map.assign(N, vector<pair<int, int>>(0));
	for (int i = 0; i < M; i++) {
		int n1, n2, val;
		cin >> n1 >> n2 >> val;
		map[n1-1].push_back({ n2-1,val });
	}

	for (int i = 0; i < N; i++)
		dijkstra(i);

	int Max = -21e8;
	for (int i = 0; i < N; i++)
	{
		int Sum = result[i][X] + result[X][i];
		if (Max < Sum) Max = Sum;
	}
	cout << Max;
	return 0;
}

수정 전에는 result 배열을 이차 배열을 사용하여 모두 저장해두었는데, 통과는 되지만 메모리를 많이 사용하는 것 같았다. 따라서 아래와 같이 일차배열을 사용하면서 다익스트라를 한번 실행할 때마다 수정해주는 것으로 변경하였다. X에서 다른 정점 사이의 최단 거리만 xResult 배열을 사용하여 저장해두고, 나머지 정점들에서의 최단 경로는 계속 갱신해주었다. 결과적으로 메모리 사용량이 1/3 정도로 감소되었다.

 

나의 풀이(수정 후):

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int NOT = 999999;

int N, M, X;
vector<vector<pair<int, int>>>map; //간선 정보
vector<int>result; //전광판
vector<int>xResult; //X에서 모든 정점들까지의 전광판

void dijkstra(int start)
{
	result.assign(N, NOT);
	result[start] = 0; //출발지
	priority_queue<pair<int, int>>pq; //{현재노드, 비용} 
	pq.push({ start,0 });
	while (!pq.empty())
	{
		int now = pq.top().first; //현재 노드(경유지) 
		int dist = -pq.top().second; //비용
		pq.pop();
		if (result[now] < dist) continue;
		for (int i = 0; i < map[now].size(); i++)
		{
			int next = map[now][i].first;
			//출발지에서 경유지 + 경유지에서 도착지
			int a = dist + map[now][i].second;
			//기존 최단 거리
			int b = result[next];
			if (a < b)
			{
				result[next] = a;
				pq.push({ next, -a });
			}
		}
	}
}

int main()
{
	cin >> N >> M >> X; //마을의수, 간선의 수, 파티 장소
	X--;
	map.assign(N, vector<pair<int, int>>(0));
	for (int i = 0; i < M; i++) {
		int n1, n2, val;
		cin >> n1 >> n2 >> val;
		map[n1-1].push_back({ n2-1,val });
	}
	
	dijkstra(X);
	xResult = result;

	int answer = -21e8;
	for (int i = 0; i < N; i++)
	{
		if (i == X) continue;
		dijkstra(i);
		answer = max(answer, xResult[i] + result[X]);
	}

	cout << answer;
	return 0;
}