[삼성기출/C++] 코드트리 투어

 

https://www.codetree.ai/training-field/frequent-problems/problems/codetree-tour?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 원래 2번 문제는 어렵지만, 이 문제는 유독 쉽게 나와서(골드2) 시도해보았고, 1번의 시도에 AC를 달성하였다!!(뿌듯) 하지만 2번 치고 쉬운 거지, 시간 초과를 유발하는 여러 시스템이 존재한다. 이 함정들을 모두 찾아내고, 해결 방법을 고민해 보자.

 

 1. 최단 거리 알고리즘으로 무엇을 채택해야 할까??

 

 우선 당연하게도, 이 문제는 최단 경로 알고리즘에서 시작한다. 최단 경로 알고리즘으로 다익스트라, 벨만 포드, 플로이드-워셜 알고리즘이 존재한다. 당연하게도 이 알고리즘은 모두 "암기"해야 한다. 하지만 보통 음의 가중치는 나오지 않으므로 급하다면 다익스트라, 플로이드-워셜만 외우고 있자. 이 문제 또한 두 알고리즘 중 하나를 적용해야하는 문제이다. 두 알고리즘의 시간복잡도는 다음과 같다.

다익스트라 : O(ElogV) (E는 간선(Edge), V는 정점(Vertex))

플로이드-워셜 : O(V^3)

 

 이러면 다익스트라가 우월한거 아닌가요? 할 수도 있겠지만 플로이드-워셜의 장점은 "모든 정점"에서 "모든 정점" 으로의 최단 경로를 구할 수 있다는 점에 있다. 대신 Vertex의 세제곱에 비례하므로, 보통 V <= 400 일때만 허용된다.

 여기서 문제의 설명을 보면, "시작 주소가 바뀔 수 있다" 고 나온다! 이걸 보고, 아, 그러면 플로이드 워셜을 써야 하는구나! 라고 생각할 수도 있다. 하지만 문제의 조건을 보면,

 

 여기에서 n <= 2000 이므로, 플로이드워셜을 쓸 수 없음을 알 수 있다. 이러면 다익스트라를 쓰라는 말인가? 그렇다. 조건을 또 자세히 보면 출발지 변경 명령은 최대 15번 주어진다고 했기 때문이다. 그러면 최단경로 찾는 시간은 15 x 2000 x log10000 이므로 상당히 안정적이다. 

 

2. 최적의 여행 상품을 O(1)에 구할 수 있을까?

 

 여기까지 왔다면, 이 문제의 최대 고비가 남았다. 문제의 조건을 또 보면, 

 

 이렇게 나온다. 즉 이러면 생기는 문제는, 다익스트라를 구할때 우선순위를 구하는 것만이 아니라, 계속 여행 상품이 생성될 때마다 다시 우선순위를 구해야 한다는 것이다! id는 30000개 까지 있으므로, 만약 30000번 의 입력이 있다면, 30000^2 만큼 우선순위를 계산해야 하므로, 시간 초과가 난다. 이를 어떻게 해결해야 할까?

 "유동적인 순위"를 구하는 것은 간단하다. 우선순위 큐를 이용하면 된다. 그런데 여기에서 귀찮은 점은, 우선순위가 다음과 같이,

 

 이득이 큰 순 -> 이득이 같으면 id가 작은 순이기 때문에 less<pair<int,int>> 로 간단하게 compare할 수 없다. 커스텀 compare 함수를 다음과 같이 작성해줘야 한다.

struct cmp {
	bool operator()(pii a, pii b) {
		if (a.first == b.first) return a.second > b.second;
		return a.first < b.first;
	}
};

priority_queue<pii, vector<pii>, cmp> cost_pq; // cost,id  : 시작지 바뀔때마다 새로 만들어야

 

 priority_queue의 compare는 배열의 compare 커스텀 함수와는 다르다. priority_queue, 즉 힙 구조에 대한 comparator를 정의하는 것이므로, 연산자 오버로딩을 해줘야 한다.

 

 여기까지 생각했으면, 이 어려운 문제를 해결할 수 있다!! 아래는 필자가 작성한 코드이다.

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
void init() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); }

int q, n, m, v, u, w, id, revenue, dest, s;
int dist_2d[2004][2004];
int dist[2004]; // 목적지까지의 SP
vector<pii> adj[2004]; // 가중치, 목적지
const int INF = 987654321;
priority_queue<pii, vector<pii>, greater<pii>> pq; // 가중치, 목적지 : 다익스트라위한 pq

pii land[30004]; // id -> {revenue,dest}
int visited[30004]; // id 들어오면 살리고, 없애면 죽이고

struct cmp {
	bool operator()(pii a, pii b) {
		if (a.first == b.first) return a.second > b.second;
		return a.first < b.first;
	}
};

priority_queue<pii, vector<pii>, cmp> cost_pq; // cost,id  : 시작지 바뀔때마다 새로 만들어야

string query;
vector<int> ret;

void dijkstra(int s) {
	fill(&dist[0], &dist[0] + 2000, INF);
	while (cost_pq.size()) cost_pq.pop();
	dist[s] = 0;
	pq.push({ 0,s });
	while (pq.size()) {
		auto a = pq.top(); pq.pop();
		int here_dist = a.first, here = a.second;
		if (dist[here] != here_dist) continue;
		for (auto b : adj[here]) {
			int there_dist = b.first, there = b.second;
			if (dist[there] > dist[here] + there_dist) {
				dist[there] = dist[here] + there_dist;
				pq.push({ dist[there], there });
			}
		}
	}
	for (int id = 1; id <= 30000; id++) {
		int revenue = land[id].first;
		int dest = land[id].second;
		if (visited[id] && revenue - dist[dest] >= 0) {
			cost_pq.push({ revenue - dist[dest], id });
		}
	}
}

void go(string query) {
	if (query == "100") {
		cin >> n >> m;
		for (int i = 0; i < m; i++) {
			cin >> v >> u >> w;
			if (dist_2d[v][u]) {
				if (w > dist_2d[v][u]) continue; // 최소가중치만 기록
			}
			dist_2d[v][u] = w;
			dist_2d[u][v] = w;
			adj[v].push_back({ w,u });
			adj[u].push_back({ w,v });
		}
	}
	if (query == "200") {
		cin >> id >> revenue >> dest;
		land[id] = { revenue,dest };
		visited[id] = true;
		if (revenue >= dist[dest]) {
			cost_pq.push({ revenue - dist[dest],id });
		}
	}
	if (query == "300") {
		cin >> id;
		visited[id] = 0;
	}
	if (query == "400") {
		while (cost_pq.size()) {
			pii a = cost_pq.top(); // cost, 목적지 id
			int id = a.second;
			cost_pq.pop();
			if (visited[id]) {
				visited[id] = 0; // 죽여주고 출력하고 리턴
				ret.push_back(id); return;
			}
		}
		ret.push_back(-1); return; // pq가 비었거나, 모두 죽었을때
	}
	if (query == "500") {
		cin >> s;
		dijkstra(s);
	}
}

int main() {
	init();
	cin >> q;
	for (int i = 0; i < q; i++) {
		cin >> query;
		go(query);
		if(i == 0) dijkstra(0);
	}
	for (int a : ret) cout << a << '\n';
	return 0;
}

 

 이번에 처음으로 2번 문제에서 1번의 시도만에 AC를 기록했다. 그동안의 노력의 결실을 맺은 것 같다.