백준 28707번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	1024MB	골드 1

---

풀이

 가지고 있는 연산으로 배열을 오름차순으로 정렬시킬 수 있는지, 또한 최소비용이 얼마인지를 알아내는 문제이다. "최소비용"을 구해야 하는 문제이다. 이 문제를 보고 들었던 방법은 매우 많다. 처음에는 백트래킹, BFS를 떠올렸고, BFS를 쓰던 중, 다익스트라로 처리를 할 수 있을 것 같았다.

 

 입력의 제한을 잘 보면 배열의 길이와 연산의 개수가 그리 크지 않다는 점을 알 수 있다. 그래서 배열을 몇번을 복사하던 그리 큰 시간이 들지 않을 것이라 판단했다. 또한 방문체크와 비용을 체크하기 위해선 배열을 만드는 것이 일반적이지만, 어떤 배열이 나올지 알 수 없기 때문에 unordered_map을 통해 기록하고자 했다. 하지만 내가 테스트를 해본 바로는, vector가 key가 될 수 없었다. 그래서 문자열로 바꿔서 key로 저장하고자 했다. 원소의 값이 10까지 나올 수 있기에 혹시 몰라서 공백을 추가하여 문자열로 변환했다. 예를 들어 {1, 2, 3} 이라는 vector 객체는 "1 2 3" 와 같이 저장되도록 말이다. 이제 다익스트라를 통해 계속해서 연산해나가도록 한다.

 

 이번 문제는 다 잘했는데, 기초적인 실수를 발견하지 못하고 계속해서 TLE를 받았다. 비용을 오름차순으로 정렬하도록 pq를 작성해야하는데, 내림차순으로 정렬되도록 작성해둔 점, pq의 top에서 데이터를 꺼냈을 때, 해당 정점으로 오는 다른 거리와 비교하여 연산을 계속할지 결정하지 않아(쉽게 말하면 중복체크를 하지 않아) 비효율적인 탐색을 한 점이다.

코드

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
using namespace std;

int n, m;
vector<int> a;
vector<tuple<int,int,int>> b;
unordered_map<string, int> visited;

void input() {
	cin >> n;
	a.resize(n);
	for(int& x : a) cin >> x;
	cin >> m;
	b.resize(m);
	for(auto& [l,r,c] : b) {
		cin >> l >> r >> c;
		--l, --r;
		if (l > r) swap(l, r);
	}
}

string vec2str(const vector<int>& v, const string& delim = " ") {
	return accumulate(ALL(v), string(), [&delim](const string& str, const int& n){
		return str + to_string(n) + delim;
	});
}

void sol() {
	priority_queue<tuple<int, int, vector<int>>> pq; // 비용, 이전 연산, 배열
	int ans = 1234567890;

	visited.insert({vec2str(a), 0});
	pq.emplace(0, -1, a);

	while(!pq.empty()) {
		auto [cur_cost, prev_op, arr] = pq.top(); pq.pop();
		string cur_key = vec2str(arr);

		if (visited[cur_key] > cur_cost) {
			continue;
		}

		if (is_sorted(ALL(arr))) {
			ans = min(ans, -cur_cost);
			break;
		}

		for(int op = 0; op < m; op++) {
			if (op == prev_op) continue;

			auto [l, r, c] = b[op];

			if (arr[l] != arr[r]) {
				swap(arr[l], arr[r]);

				string key = vec2str(arr);

				// 방문한적이 없거나, 전에 방문했을 때보다 비용이 더 적다면
				if (visited.find(key) == visited.end() || visited[key] < cur_cost - c) {
					visited[key] = cur_cost - c;
					pq.emplace(cur_cost - c, op, arr);
				}

				swap(arr[l], arr[r]);
			}
		}
	}

	cout << (ans == 1234567890 ? -1 : ans);
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	input();
	sol();
}