[BOJ] 1238 파티

1238 파티

Class	BOJ
Created	@June 11, 2020 5:50 PM
Materials	https://www.acmicpc.net/problem/1238
Property	#c++ #다익스트라
Reviewed
Type	more

접근법

일단 나는 처음에 플로이드 와샬 알고리즘을 사용했다. 다익스트라는 출발지가 정해져야 하는데 그러면 N번의 다익스트라를 해야하고 어차피 모든 정점을 출발점으로 하여 값들을 알아내야 한다면 플로이드를 써도 괜찮겠다고 생각했기 때문이다. 그런데 생각해보면 도착지(집에서 X로)나 출발지(X에서 집)가 X로 정해져있다. X가 출발지가 되는 경우에는 입력값이 들어온 대로 만들어진 map에서 다익스트라를 사용하고, X가 도착지가 되는 경우라면 입력 간선들을 뒤집어서 만든 map에서 X를 출발지로 생각하고 다익스트라를 사용하면 된다.(!!)

CODE

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#define MXM 1001
#define INF 987654321

int main() {
	vector<pair<int,int>> go_x[MXM], home[MXM];
	int n, m ,x; n = readInt(); m =readInt(); x = readInt();
	int a, b, t;
	while(m--){
		a = readInt(); b = readInt(); t = readInt();
		go_x[a].push_back({t,b});
		home[b].push_back({t,a});
	}
	priority_queue<pair<int,int>> pq;
	int dist_f[MXM], dist_b[MXM];
	for(int i = 1; i <= n; i++)
		dist_f[i] = dist_b[i] = INF;
	dist_f[x] = dist_b[x] = 0;
	pair<int,int> node, next;
	pq.push({0, x}); //dist, node
	while(!pq.empty()){
		node = pq.top(); pq.pop(); node.first *= -1;
		if(node.first > dist_f[node.second])	continue;
		for(register int i = 0; i < go_x[node.second].size(); i++)
		{	
			next = go_x[node.second][i];
			if(dist_f[next.second] > node.first + next.first)
			{
				dist_f[next.second] = node.first + next.first;
				pq.push({-dist_f[next.second], next.second});
			}
		}
	}
	pq.push({0,x});
	while(!pq.empty()){
		node = pq.top(); pq.pop(); node.first *= -1;
		if(node.first > dist_b[node.second])	continue;
		for(register int i =0; i < home[node.second].size(); i++){
			next = home[node.second][i];
			if(dist_b[next.second] > node.first + next.first)
			{
				dist_b[next.second] = node.first + next.first;
				pq.push({-dist_b[next.second], next.second});
			}
		}
	}
	int ans = 0;
	for(int i =1; i <= n; i++)
		if(i != x && ans < dist_f[i] + dist_b[i])
			ans = dist_f[i] + dist_b[i];
	printf("%d",ans);
	return 0;
}
				//5036KB , 672ms -> 2244KB, 0ms

---

• vertex가 최대 1000개밖에 안되서 플로이드로도 풀 수 있었던 것 같다(하지만 문제에서 원하는 풀이 방법은 아닌 것 같다). 노드와 간선 수가 최대 1000, 10000정도라 다익스트라 시 일반 큐, 그냥 일반 BFS처럼 풀어도 실행 시간에 큰 차이가 없는 것 같다. 일반 큐를 사용한 사람들은 pair대신 struct를 생성해서 사용하던데, 나는 우선순위 큐를 사용했다가 pair를 struct로 바꾸려다가 에러 날 거라는 걸 나중에 알았다....

  일반 큐 : O(E+V^2) 우선순위 큐 : O(ElogV)

• 다른 정답 소스랑 비교해보면 메모리 차이가 좀 심하다. 일단 2번째 줄을 삭제하고 (왜 안 지웠지?), inline함수를 통해 입력값을 받아서 코드 길이가 늘어나서 그런 것 같다. 근데 다른 코드보니까 scanf써도 실행 시간은 똑같더라. 이런거 다 고치면 많이 줄어들 것 같다. (시도는 안해봄)