[백준] 1238번 파티

문제: 1238번: 파티

 

• 내 코드: 다익스트라 n+1 번 돌리는 코드..

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>

using namespace std;

// 연결 정보를 저장하기 위한 linkedList
// first: 가중치, second: 연결정점
// 0 번 인덱스는 안 쓸 것. 인덱스 계산 편하게 하기 위해 1001 만큼의 공간 잡음
vector<pair<int, int>> linkedList[1001];

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

	int n, m, x; // n: 마을 개수, m: 단 방향 도로 개수, x: 파티 장소
	cin >> n >> m >> x;
	
	// 도로 정보 반영해주기
	for (int i = 0; i < m; i++) {
		int from, end, t; // from: 도로 시작점, end: 도로 끝점, t: 소요시간
		cin >> from >> end >> t;

		// 도로 끝점과 소요시간을 묶어서 linkedList 에 저장..
		linkedList[from].push_back(make_pair(t, end));
	}

	// 음.. 일단 파티 장소에서 다른 정점으로 돌아가는 걸 다익스트라로 구하자..
	vector<int> distance = vector<int>((n + 1), INT_MAX); // 0 번 인덱스는 안 쓸 것..

	// 갈 수 있는 연결선들을 저장해놓기 위함
	// 최소힙으로 동작하도록(가중치를 기준으로)
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minNodes;
	minNodes.push(make_pair(0, x)); // 시작점에서 시작점으로의 거리는 0임..
	distance[x] = 0; // 거리 저장 배열에도 반영해놓기..

	// 집합에 이미 선택된 마을 번호 저장해놓기..
	set<int> nodeNums;

	// 갈 수 있는 연결선이 존재하는 동안..
	while (!minNodes.empty()) {
		pair<int, int> edge = minNodes.top();
		minNodes.pop();

		int u = edge.second;

		// find 함수는 해당 요소가 집합에 존재하지 않을 때 end() 를 반환 함..
		// 이미 존재하면 포기하기 위해서 != 조건을 씀..
		if (nodeNums.find(u) != nodeNums.end()) continue;

		// 존재하지 않는다면 집합에 넣기
		nodeNums.insert(u);
		
		// 이제 새로 넣은 애랑 연결되어 있는 정점들 정보 업데이트
		for (int i = 0; i < linkedList[u].size(); i++) {
			int w_uv = linkedList[u][i].first; // u 와 v 연결 가중치
			int v = linkedList[u][i].second;

			// 만약 집합에 존재하지 않고, 기존 거리보다 현재 갱신해주려고 하는 값이 더 작으면 정보 업데이트
			if ((nodeNums.find(v) == nodeNums.end()) && (distance[u] + w_uv < distance[v])) {
				distance[v] = distance[u] + w_uv;
				minNodes.push(make_pair(distance[v], v));
			}
		}
	}
	
	// distance 에는 파티 장소에서 각 집으로 돌아가는데 걸리는 시간 저장되어 있음.
	// 그럼 각 점에서 파티 장소로 오는데 걸리는 시간은 어떻게 구함..?
	// 설마 각 정점을 시작점으로 해서 x번으로 가는데 걸리는 최소 시간을 각각 구해야하??
	int start = 0;
	vector<int> tmpDistance((n + 1), INT_MAX);
	set<int> tmpNodeSet;
	int maxDistance = INT_MIN; // 오고 가는데 가장 오래 걸리는 학생의 소요시간
	
	for (int i = 1; i < n + 1; i++) {
		if (i == x) continue; // 자기 자신으로 돌아가는건 어차피 0인데 구할 필요 있나..

		start = i; // 이제 시작 정점을 i 로 생각하고 다시 다익스트라..
		tmpDistance = vector<int>((n + 1), INT_MAX); // 초기화..
		tmpDistance[start] = 0; // 자기 자신으로의 거리는 0

		minNodes = priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>(); // 새로 만들어주기..
		minNodes.push(make_pair(0, start)); // 시작점에서 시작점으로의 거리는 0

		tmpNodeSet = set<int>(); // 집합도 초기화 ㅎ..;;

		// 갈 수 있는 연결선이 존재하는 동안..
		while (!minNodes.empty()) {
			pair<int, int> edge = minNodes.top();
			minNodes.pop();

			int u = edge.second;

			// find 함수는 해당 요소가 집합에 존재하지 않을 때 end() 를 반환 함..
			// 이미 존재하면 포기하기 위해서 != 조건을 씀..
			if (tmpNodeSet.find(u) != tmpNodeSet.end()) continue;

			// 존재하지 않는다면 집합에 넣기
			tmpNodeSet.insert(u);

			// 이제 새로 넣은 애랑 연결되어 있는 정점들 정보 업데이트
			for (int i = 0; i < linkedList[u].size(); i++) {
				int w_uv = linkedList[u][i].first; // u 와 v 연결 가중치
				int v = linkedList[u][i].second;

				// 만약 집합에 존재하지 않고, 기존 거리보다 현재 갱신해주려고 하는 값이 더 작으면 정보 업데이트
				if ((tmpNodeSet.find(v) == tmpNodeSet.end()) && (tmpDistance[u] + w_uv < tmpDistance[v])) {
					tmpDistance[v] = tmpDistance[u] + w_uv;
					minNodes.push(make_pair(tmpDistance[v], v));
				}
			}
		}

		// 이제 tmpDistance 배열에서 인덱스 x번 값 가져온다음에 distnace 요소에 더해주기.. ㅎㅎ;;
		distance[start] += tmpDistance[x]; // 이게 start 에서 파티가 일어나는 장소로 가는 거리
		if (distance[start] > maxDistance)
			maxDistance = distance[start];
	}
	cout << maxDistance << "\n";


	return 0;
}

 

일단 x(파티가 열리는 마을) 을 시작점으로 해서 다익스트라로 돌리면 distance 에는 나머지 정점으로 가는데 걸리는 시간이 저장된다. 그렇다면 각 정점에서 x 정점으로 가는 데 걸리는 시간은 어떻게 구할 수 있을까?

 

내가 푼 방식은 반복문을 돌면서 start 를 각각의 정점으로 주었다. 즉, 각 정점을 start 로 설정해서 다익스트라를 돌렸다. 돌린 다음에 tmpDitance 배열에 저장되어 있는 x 번째 요소값이 바로 각 정점에서 x 정점으로 가는데 걸리는 시간이다.

 

근데 위 방식은 다익스트라를 n+1 번 사용하는 방식이라 스스로 코드를 짜면서도 문제의 의도는 이게 아닌 것 같다는 생각이 들었다;; n 의 최대 범위가 1000 인 걸 생각해서 내 코드도 정상적으로 작동할 건 알고 있었지만 그래도 더 똑똑한 풀이법을 알고 싶었다.

 

그래서 찾아본 결과 다익스트라를 2번만 돌려서 값을 구할 수 있었다. 어떻게 이게 가능한지 봤더니 역방향 간선 다익스트라를 이용한다고 한다. 즉, 원래 입력으로 주어진 간선들을 역방향으로 하는 linkedList 를 하나 더 만들어서 이를 기준으로 다익스트라 한 번 돌리고, 다음으로 원래 입력으로 다익스트라 한 번 돌려서 총 2번으로 답을 구할 수 있는 것이었다.

 

.. 새롭게 알게되어서 좋았다. 이번에 알게 되었으니까 다음에 써볼 기회가 있으면 좋겠다.  

 

 

 

참고자료:

• 역방향 간선 다익스트라 이용

[C++] 백준 1238번 - 파티

[C++] 백준 1238번 - 파티