[백준] 11265 - 끝나지 않는 파티

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

11265번: 끝나지 않는 파티

 

알고리즘 방식

• 플로이드 워셜 방식으로 구현이 가능한 알고리즘이며
  다익스트라를 활용해도 구현이 가능한 알고리즘이였다.

먼저 정점의 개수는 V, 간선의 개수는 E이며, V^2 >= E가 성립한다.

다익스트라의 경우 시간복잡도는 O(ElogV)이다.

플로이드 워셜의 경우 시간복잡도는 O(E^3)이다.

 

다익스트라를 활용한 풀이의 경우 기본 다익스트라 알고리즘에 for문을 씌웠기 때문에 O(VElogV)로 시간복잡도가 O(V^3)인 플로이드 워셜보다 빠를거라 생각했다. 하지만, 플로이드 워셜이 훨씬 빨랐다.

이에대해 고찰해봤는데, 핵심은 간선의 개수에 있었다. 플로이드 워셜은 간선의 개수와 상관없이 시간복잡도가 일정하지만, 다익스트라의 경우 시간복잡도가 간선의 개수에 영향을 많이 받을 수 밖에 없기 때문에, 간선의 개수가 적을 경우 전자가 더 빠르겠지만, 간선의 개수가 많아질 경우 플로이드 워셜이 더 빠르다.

 

소스코드

for문을 씌운 다익스트라

#include <iostream>
#include <vector>
#include <queue>
#define INF 987654321
 
using namespace std;
 
int N, M;
vector<vector<int>> node;
vector<vector<int>> val;
vector<string> answer;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
 
//n*nlogn
void daijkstra() {
	for (int from = 0; from < N; from++) {
		pq.push({ 0, from });
		val[from][from] = 0;
 
		while (!pq.empty()) {
			int disSum = pq.top().first;
			int loc = pq.top().second;
			pq.pop();
 
			for (int to = 0; to < N; to++) {
				int x = node[loc][to];
				if (disSum + x < val[from][to]) {
					val[from][to] = disSum + x;
					pq.push({ val[from][to], to });
				}
			}
		}
	}
}
 
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
 
	cin >> N >> M;
	node.assign(N, vector<int>(N, 0));
	val.assign(N, vector<int>(N, INF));
 
 
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> node[i][j];
		}
	}
 
	daijkstra();
 
	int A, B, C;
	for (int i = 0; i < M; i++) {
		cin >> A >> B >> C;
 
		if (val[A - 1][B - 1] <= C)
			answer.push_back("Enjoy other party\n");
		else
			answer.push_back("Stay here\n");
	}
 
	for (auto v : answer)
		cout << v;
}

플로이드-워셜

#include <iostream>
#include <vector>
#include <queue>
#define INF 987654321
 
using namespace std;
 
int N, M;
vector<vector<int>> floyd;
vector<string> answer;
 
//n^3
void FloydWarshall() {
	for (int by = 0; by < N; by++) {
		for (int from = 0; from < N; from++) {
			for (int to = 0; to < N; to++) {
				if (floyd[from][by] + floyd[by][to] < floyd[from][to])
					floyd[from][to] = floyd[from][by] + floyd[by][to];
			}
		}
	}
}//from by to
 
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
 
	cin >> N >> M;
	floyd.assign(N, vector<int>(N, 0));
 
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> floyd[i][j];
		}
	}
 
	FloydWarshall();
 
	int A, B, C;
	for (int i = 0; i < M; i++) {
		cin >> A >> B >> C;
 
		if (floyd[A - 1][B - 1] <= C)
			answer.push_back("Enjoy other party\n");
		else
			answer.push_back("Stay here\n");
	}
 
	for (auto v : answer)
		cout << v;
}