백준 1238 파티

1. 문제 링크

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

1238번: 파티

 

2.  풀이

 

N명의 사람(노드) / M개의 경로(단방향) 그래프와 X(노드 번호)가 주어졌을 때,

1. [모든 사람 -> X]의 최단거리
2. [X -> 모든 사람]의 최단거리 

를 구하는 것이 핵심인 문제이다.

[X -> 모든 사람]의 최단 거리의 경우 X를 출발점으로 하는 다익스트라 알고리즘을 쉽게 떠올렸다. 

 

하지만 반대의 경우 출발 지점이 모든 사람이기 때문에 플로이드 와샬 알고리즘을 통해 모든 정점 사이의 최단거리를 구해야 하는 것 아닌가 생각을 했었다.(플로이드 와샬 알고리즘은 O(n^3)의 비 효율적인 시간 복잡도를 가진다.)

 

그런데, 조금 더 고민해 보니 [모든 사람 -> X]의 최단거리 의 경우도 

 

그래프 상 단방향 경로의 방향을 반대로 바꾸게 되면

 

[X -> 모든 사람]의 최단거리와 동일한 다익스트라 알고리즘을 통해 구할 수 있음을 알게 되었다!.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Element {
public :
	int node, weight;
	Element() {};
	Element(int node, int weight) {
		this->node = node;
		this->weight = weight;
	};
};

struct compare {
	bool operator()(const Element& lhs, const Element& rhs) const {
		return lhs.weight > rhs.weight;
	}
};

const unsigned int MAX_INT = 2000000000;
int N, M, X;

void InputAndInit(vector<Element> graph1[1001], vector<Element> graph2[1001], int homeToX[], int XToHome[]) {
	cin >> N >> M >> X;
	for (int i = 1; i <= N; i++) {
		graph1[i].clear();
		graph2[i].clear();

		homeToX[i] = MAX_INT;
		XToHome[i] = MAX_INT;
	}
	int start, end, weight;
	for (int i = 0; i < M; i++) {
		cin >> start >> end >> weight;
		graph1[start].push_back({ end,weight });
		graph2[end].push_back({ start,weight });
	}
}



void Dijkstra(vector<Element> graph[], int arr[]) {
	priority_queue<Element, vector<Element>, compare> pq;
	bool visited[1001];
	for (int i = 0; i < 1001; i++)
		visited[i] = false;

	pq.push({ X,0 });
	arr[X] = 0;
	while (!pq.empty()) {
		Element currentE = pq.top(); pq.pop();
		visited[currentE.node] = true;

		for (Element nextE: graph[currentE.node]) {
			if (arr[currentE.node] + nextE.weight >= arr[nextE.node])
				continue;
			if (visited[nextE.node])
				continue;

			arr[nextE.node] = arr[currentE.node] + nextE.weight;
			pq.push({ nextE.node , arr[currentE.node] + nextE.weight });
		}
	}
}

int Answer(int homeToX[], int XToHome[]) {
	int max = 0;
	for (int i = 1; i <= N; i++) {
		max = max > (XToHome[i] + homeToX[i]) ? max : (XToHome[i] + homeToX[i]);
	}
	return max;
}

int main() {
	vector<Element> graph1[1001];
	vector<Element> graph2[1001];
	int homeToX[1001];		//X로 가는 최단거리(출발지: 각각의 집)
	int XToHome[1001];		//X에서 각 집으로 가는 최단거리(출발지: X)
	InputAndInit(graph1, graph2, homeToX, XToHome);
	Dijkstra(graph1, homeToX);
	Dijkstra(graph2, XToHome);
	cout << Answer(homeToX, XToHome) << "\n";
}

 

하나의 출발점에서 모든 정점으로의 최단 거리는 다익스트라 알고리즘을 통해 구할 수 있다.

 

이를 조금 더 응용하여,

 

단방향 그래프의 경우 방향의 위치를 반대로 하게 되면, 모든 정점에서 하나의 지점까지의 최단거리도 구할 수 있음을 이해하자.