백준 1238번: 파티

[문제 링크]

1238번: 파티

---

방향그래프를 만든 다음 최단 경로 알고리즘을 통해 간단히 풀 수 있는 문제였다.

 

처음 풀었을 땐 플로이드-와샬 알고리즘으로 구현해서 정답을 받았는데, 생각해보니 N이 최대 1000이기 때문에 시간복잡도가 O(N^3)인 플로이드-와샬 알고리즘을 사용하면 최악의 경우 10억만큼의 시간이 걸리게 된다. 입력데이터가 부실했기 때문에 운좋게 통과했다고 생각한다.

 

따라서 다익스트라 알고리즘을 사용해서 다시 구현하였다.

 

//추가 : 질문게시판에서 시간복잡도를 더 줄이는 방법에 대한 힌트를 발견하였다.

도착지점이 X로 정해져 있기 때문에 모든 정점의 최단 경로를 다 구할 필요 없이 정점으로 들어오는 간선들의 집합과 정점에서 나가는 간선들의 집합을 분리한 다음, 정점 X에서 들어오는 간선과 나가는 간선을 대상으로 두번의 다익스트라를 수행하면 문제를 해결할 수 있다.

---

// 플로이드-와샬 알고리즘 사용

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 987654321;
vector<vector<int>> adj(1001, vector<int>(1001, INF));

void floyd(int N) {
	for (int i = 1; i <= N; i++) {
		adj[i][i] = 0;
	}

	for (int k = 1; k <= N; k++)
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}

int main(void) {
	int N, M, X;
	cin >> N >> M >> X;

	for (int i = 0; i < M; i++) {
		int A, B, W;
		cin >> A >> B >> W;
		adj[A][B] = W;
	}

	floyd(N);

	int result = 0;
	for (int i = 1; i <= N; i++) {
		result = max(result, adj[i][X] + adj[X][i]);
	}

	cout << result << endl;

	return 0;
}

 

// 다익스트라 알고리즘 사용

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = 987654321;
int N, M, X;
vector<pair<int, int>> adj[1001];
vector<vector<int>> allTownDist(1001);

void dijkstra(int start) {
	vector<int> dist(N+1, INF);
	dist[start] = 0;
	
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });

	while (!pq.empty()) {
		int here = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();

		if (dist[here] < cost) continue;
		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].first;
			int nextCost = adj[here][i].second + cost;

			if (dist[there] > nextCost) {
				dist[there] = nextCost;
				pq.push({ -nextCost, there });
			}
		}
	}

	allTownDist[start] = dist;
}

int main(void) {
	cin >> N >> M >> X;

	for (int i = 0; i < M; i++) {
		int A, B, W;
		cin >> A >> B >> W;
		adj[A].push_back({ B, W });
	}

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

	int result = 0;
	for (int i = 1; i <= N; i++) 
		result = max(result, allTownDist[i][X] + allTownDist[X][i]);

	cout << result << endl;

	return 0;
}

 

// 다익스트라 2번으로 문제를 해결하는 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = 987654321;
int N, M, X;
vector<pair<int, int>> adjIn[1001];
vector<pair<int, int>> adjOut[1001];

vector<int> inDist(1001);
vector<int> outDist(1001);

void dijkstra(int start, int type) {
	vector<int> dist(N + 1, INF);
	dist[start] = 0;

	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });
	
	if (type == 1) {
		while (!pq.empty()) {
			int here = pq.top().second;
			int cost = -pq.top().first;
			pq.pop();

			if (dist[here] < cost) continue;
			for (int i = 0; i < adjIn[here].size(); i++) {
				int there = adjIn[here][i].first;
				int nextCost = adjIn[here][i].second + cost;

				if (dist[there] > nextCost) {
					dist[there] = nextCost;
					pq.push({ -nextCost, there });
				}
			}
		}
		inDist = dist;
	}

	else {
		while (!pq.empty()) {
			int here = pq.top().second;
			int cost = -pq.top().first;
			pq.pop();

			if (dist[here] < cost) continue;
			for (int i = 0; i < adjOut[here].size(); i++) {
				int there = adjOut[here][i].first;
				int nextCost = adjOut[here][i].second + cost;

				if (dist[there] > nextCost) {
					dist[there] = nextCost;
					pq.push({ -nextCost, there });
				}
			}
		}
		outDist = dist;
	}
}

int main(void) {
	cin >> N >> M >> X;

	for (int i = 0; i < M; i++) {
		int A, B, W;
		cin >> A >> B >> W;
		adjIn[A].push_back({ B, W });
		adjOut[B].push_back({ A, W });
	}

	dijkstra(X, 1); // 정점으로 들어오는 간선들의 최단경로
	dijkstra(X, 2); // 정점에서 나가는 간선들의 최단경로

	int result = 0;
	for (int i = 1; i <= N; i++) 
		result = max(result, inDist[i] + outDist[i]);

	cout << result << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 167 day