[C/C++] 백준 - 1238번 : 파티 (다익스트라 알고리즘)

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

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

 

파티를 몇번 마을에서 하는지는 문제에 입력으로 주어지기 때문에 우리는 모든 마을을 시작지점으로 지정해서 다른 마을까지의 모든 최단경로를 구해주면 된다. 그리고 파티가 일어나는 마을에서 다시 되돌아오는 거리까지 고려해야하기 때문에 파티마을을 시작지점으로 지정하고 다른 마을까지의 최단경로 또한 구해주어야한다.

 

나는 각 마을의 최단거리를 모두 구해주어야하기 때문에 2차원 배열에 그 거리들을 저장해주었다.

Cost[i][j] -> i가 시작 마을로 지정되었을 때, j마을까지의 거리

문제 예제로 한 번 내가 해결한 과정을 보자면, 입력으로 주어지는 정보로 알 수 있는 것은

 

◎ 1번 마을에서 갈 수 있는 다른 마을 :

   - 2번 마을(4), 3번 마을(2), 4번 마을(7)

 

◎ 2번 마을에서 갈 수 있는 다른 마을 :

   - 1번 마을(1), 3번 마을(5)

 

◎ 3번 마을에서 갈 수 있는 다른 마을 :

   - 1번 마을(2), 4번 마을(4)

 

◎ 4번 마을에서 갈 수 있는 다른 마을 :

   - 2번 마을(3)

 

으로 나타낼 수 있다. 그럼 이제 각 마을을 시작지점으로 모든 마을의 최단경로를 구해보자.

 

첫 번째로 1번 마을을 시작지점으로 지정하고, 다른 마을까지 경로를 구하면 일단, 1번 마을이 시작지점이므로 1번마을의 비용은 0이 된다(1번 마을 -> 1번 마을 ; 같으므로)

1번 마을	2번 마을	3번 마을	4번 마을
0	4	2	7

이제 다익스트라 알고리즘을 적용해서, 이 중에서 가장 비용이 적은 3번 마을을 거쳐 최소비용으로 다른 마을을 갈 수 있는지 확인해본다.

1번 마을에서 3번 마을 가는 비용(2) + 3번 마을에서 다른 마을 가는 비용(?)이 1번 마을에서 다른 마을 가는 비용보다 적다면 그 값으로 최신화 시켜주는 것이다.

3번 마을에서 갈 수 있는 마을이 1번 마을, 4번 마을이 존재하는데 1번 마을은 어처피 시작지점으로 비용이 0이기 때문에 더 작을 수 없고 4번 마을은 비용이 4이다. 1번에서 3번 마을 오는 비용(2) + 3번 마을에서 4번 마을 가는 비용(4)=6이 1번 마을에서 다이렉트로 4번 마을까지 가는 비용(7)보다 작으므로 최신화 해준다.

1번 마을	2번 마을	3번 마을	4번 마을
0	4	2	6

이제 이와 같은 과정으로 모든 마을을 시작지점으로 잡고 반복해주면

Cost[i][j]	1번 마을	2번 마을	3번 마을	4번 마을
1번 마을이 시작지점	0	4	2	6
2번 마을이 시작지점	1	0	3	7
3번 마을이 시작지점	2	6	0	4
4번 마을이 시작지점	4	3	6	0

으로 나타낼 수 있다.

 

그럼 이 문제에서 최종적으로 구해야 할 파티가 열리는 마을까지 갔다가 되돌아오는데 가장 비용이 큰 값을 구하자면

int Answer_Cost = 0;
for (int i = 1; i <= N; i++) {
	if (i == X) continue;
	Answer_Cost = max(Answer_Cost, Cost[X][i] + Cost[i][X]);
}

으로 구할 수 있다.

 

< 코드 >

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#define INF 9876543210
#define ENDL cout << endl;
#define endl '\n'
#define swap(type, x, y) do{type t=y;y=x;x=t;}while(0)
using namespace std;

typedef long long ll;
typedef pair<int, int> pl;

struct cmp {
	bool operator()(pl a, pl b) {
		if (a.first == b.first) return a.second > b.second;
		return a.first > b.first;
	}
};

int N, M, X;
int Cost[1001][1001];
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;

typedef struct graphNode {
	int dest;
	int cost;
	struct graphNode* next;
}GraphNode;

typedef struct graph {
	int count;
	GraphNode* adj;
}Graph;

void Graph_Init(Graph* gph, int count) {
	gph->count = count;
	gph->adj = (GraphNode*)malloc(sizeof(GraphNode) * (count + 1));
	for (int i = 1; i <= count; i++) 
		gph->adj[i].next = NULL;
}

int AddDirectedLinkedEdge(Graph* gph, int src, int dst, int cost) {
	GraphNode* Temp = (GraphNode*)malloc(sizeof(GraphNode));
	Temp->cost = cost;
	Temp->dest = dst;
	Temp->next = gph->adj[src].next;
	gph->adj[src].next = Temp;
	return 1;
}

void Find_Cost(Graph* gph, int prev, int Edge, int idx) {
	GraphNode* head = gph->adj[Edge].next;
	while (head) {
		if (prev + head->cost < Cost[idx][head->dest]) {
			Cost[idx][head->dest] = prev + head->cost;
			pq.push({ Cost[idx][head->dest], head->dest });
		}
		head = head->next;
	}
}

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

	cin >> N >> M >> X;
	Graph graph;
	Graph_Init(&graph, N);
	for (int i = 0; i < M; i++) {
		int start, end, cost;
		cin >> start >> end >> cost;
		AddDirectedLinkedEdge(&graph, start, end, cost);
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) Cost[i][j] = 0;
			else Cost[i][j] = INF;
		}
		pq.push({ 0,i });
		while (!pq.empty()) {
			int prev_cost = pq.top().first;
			int next_Edge = pq.top().second;
			pq.pop();

			Find_Cost(&graph, prev_cost, next_Edge, i);
		}
	}

	int Answer_Cost = 0;
	for (int i = 1; i <= N; i++) {
		if (i == X) continue;
		Answer_Cost = max(Answer_Cost, Cost[X][i] + Cost[i][X]);
	}
	cout << Answer_Cost << endl;

	return 0;
}