BOJ 13308 : 주유소

3줄요약

• 다익스트라 (Similar to KCM Travel, but has lil different)
• dfs인줄 알았는데 또익스트라

 

서론

 

다익스트라 문제이다. 이 문제는 영양가가 넘쳤다. KOI 2016 고등부 2번문제이기도 하고, (나는 중학생이지만) 다익스트라와 기본적인 사고방식을 성장시키기 좋은 문제였다.

 

본론

 

기본적인 다익스트라 문제와는 다르게, 이 문제는 다익스트라를 2번 실행해야 한다.

첫 번째로 모든 정점에서부터 j번째 정점으로 가는 최단거리를 구하는 다익스트라, ( 시간복잡도: O(V * E * log(V) )

두 번째로 첫 번째에서 구한 dist[i][j] 배열을 토대로 1번 정점에서 V번 정점으로 가는 최단거리를 구하는 다익스트라이다. ( 시간복잡도: O (V^2 * log(V) )

 

이해가 안 갈 수 있는데, 예제에서 첫 번째 다익스트라를 실행하면,

 

dist[i][j] 배열

 

이렇게 되고,

 

예제에서 두 번째 다익스트라를 실행하면,

 

dist[i][j] 에서 최단거리를 구한 dp[i]

 

이렇게 된다. (dp[i] = i번 정점에서부터 1번 정점까지의 최단거리) 따라서, 답은 dp[V]가 된다. 정답 코드는 밑에 첨부했다.

 

 

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
#define MAXV 2501
#define MAXE 5001
#define INF 4223372036854775807
#define ll long long
#define pp pair<ll, ll>

ll V, E;
vector<pp> graph[MAXV];
ll cost4city[MAXV];
ll dist[MAXV][MAXV];
ll dp[MAXV];
bool chk[MAXV];

void djikstra(ll node) {
	
	
	priority_queue<pp, vector<pp>, greater<pp> > pq;
	pq.push( {0, node} ); // cost, node
	
	while (!pq.empty()) {
		
		ll cost = pq.top().first;
		ll nownode = pq.top().second;
		pq.pop();
		
		if (dist[node][nownode] < cost) continue;
		
		for (ll i = 0; i < graph[nownode].size(); i++) {
			
			ll to = graph[nownode][i].second;
			ll to_cost = cost + (ll)(graph[nownode][i].first * cost4city[node]);
			
			if (to_cost < dist[node][to]) {
				
				dist[node][to] = to_cost;
				pq.push( { to_cost, to } );
				
			}
		}
	}
	
}

int main() {
	
	scanf("%lld %lld", &V, &E);
	for (ll i = 1; i <= V; i++) {
		scanf("%lld", &cost4city[i]);
	}
	
	for (ll i = 0; i < E; i++) {
		
		ll from, to, cost;
		scanf("%lld %lld %lld", &from, &to, &cost);
		graph[from].push_back( { cost, to } );
		graph[to].push_back( { cost, from } );
	}
	
	for (ll i = 1; i <= V; i++) for (ll j = 1; j <= V; j++) dist[i][j] = i == j ? 0 : INF;
	
	for (ll i = 1; i <= V; i++) { // N^2logN, fuck Floyd
		djikstra(i);
	}
	
	for (ll i = 1; i <= V; i++) {
		dp[i] = INF;
	}
	
	// dfs -> second djikstra
	vector<pp> djikgraph[MAXV]; // cost, node
	for (ll i = 1; i <= V; i++) for (ll j = 1; j <= V; j++) if (i != j) djikgraph[i].push_back({j, dist[i][j]});

	
	priority_queue<pp, vector<pp>, greater<pp> > pq;
	pq.push( { 0, 1 } ); // cost, node
    dp[1] = 0;
    
	while (!pq.empty()) { // 최단거리 한번 더 구하기:  dp[x] = dist[x] = 동의어 
		
		ll node = pq.top().second;
		ll cost = pq.top().first;
		pq.pop();
		
		if (dp[node] < cost) continue;
		
		for (ll i = 0; i < djikgraph[node].size(); i++) {
			
			ll to = djikgraph[node][i].first;
			ll to_cost = cost + djikgraph[node][i].second;
			
			if (dp[to] > to_cost) {
				dp[to] = to_cost;
				pq.push({ to_cost, to });
			}
		}
		
	}
	
	printf("%lld", dp[V]);
}

 

 

결론

 

여담으로, 나는 두 번째 다익스트라를 실행하는 과정을 dfs로 대체했다가 8번 연속 16점 세례를 맞았다. 뒤늦게 dfs가 안 된다는 사실을 깨닫고는 빠르게 다익스트라로 대체했다.

별개로, 나는 알고리즘을 잘하는 방법이 생각의 폭을 넓히는 것이라고 생각한다. 내가 이 문제를 어떤 알고리즘으로 풀 수 있을지 생각하고, 어떻게 이 알고리즘을 활용할 수 있을지 생각하는 기술이 필요하다. 당연히 이 기술을 늘리려면 이 알고리즘이 어떨 때 쓰이는 것인지 알 필요가 있다. dp는, 부분 문제로 나타내어 풀 수 있을 때라던지, 그리디는 항상 좋은 선택을 해도 문제를 풀 수 있을 때라던지, 이다. 그리고 알고리즘을 잘하려면 창의적으로 생각하는 기술이 필요하다.

 

나는 첫번째 기술은 충족했다고 어느정도 생각하지만, 두 번째 기술이 모자라다고 생각하여, 그리디, 분할 정복, dp, 수학 관련 문제를 많이 풀 예정이다.

 

난이도(개인적): Platinum V

난이도(객관적): Platinum V

 

Contact: How2Contact (tistory.com)