취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25140번 문제인 KLIZA이다.
문제는 아래 링크를 확인하자.

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

칸을 이동해 만들어질 수 있는 각 상태를 노드로, 한 번의 조작으로 서로 바뀔 수 있는 관계를 양방향 에지로 하는 그래프를 모델링해보자. 이때, 주어진 상태에서 초기 상태를 만들기 위해 필요한 조작의 수는 위 그래프에서의 최단거리와 같음을 알 수 있다.

가능한 상태의 경우의 수는 9팩토리얼의 upper bound를 갖고(실제로는 이보다 더 적다), 각 상태에서 한 번의 조작으로 얻을 수 있는 다음 상태는 많아야 네 가지이므로 노드의 수와 에지의 수가 충분히 적음을 관찰하자. 따라서 위 그래프에서의 BFS 등을 이용해 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;

vector<int> vecS(9);
vector<int> vecE(9);
map<vector<int>, int> mp;
map<vector<int>, int> btrk;
queue<vector<int>> que;

void bfs() {
	mp[vecS] = 0;
	que.push(vecS);
	while (!que.empty()) {
		auto cur = que.front(); que.pop();
		int d = mp[cur];
		int idx = 0; while (cur[idx] != 9) idx++;
		if (idx - 3 >= 0) {
			swap(cur[idx], cur[idx - 3]);
			if (!mp.count(cur)) {
				mp[cur] = d + 1;
				que.push(cur);
				btrk[cur] = cur[idx];
			}
			swap(cur[idx], cur[idx - 3]);
		}
		if (idx + 3 < 9) {
			swap(cur[idx], cur[idx + 3]);
			if (!mp.count(cur)) {
				mp[cur] = d + 1;
				que.push(cur);
				btrk[cur] = cur[idx];
			}
			swap(cur[idx], cur[idx + 3]);
		}
		if (idx % 3) {
			swap(cur[idx], cur[idx - 1]);
			if (!mp.count(cur)) {
				mp[cur] = d + 1;
				que.push(cur);
				btrk[cur] = cur[idx];
			}
			swap(cur[idx], cur[idx - 1]);
		}
		if (idx % 3 < 2) {
			swap(cur[idx], cur[idx + 1]);
			if (!mp.count(cur)) {
				mp[cur] = d + 1;
				que.push(cur);
				btrk[cur] = cur[idx];
			}
			swap(cur[idx], cur[idx + 1]);
		}
	}
}

vector<int> ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 9; i++) {
		char c; cin >> c;
		if (c == 'X') c = '9';
		vecS[i] = c - '0';
	}
	for (int i = 0; i < 9; i++) vecE[i] = i + 1;
	bfs();

	cout << mp[vecE] << '\n';
	while (btrk.count(vecE)) {
		int x = btrk[vecE];
		ans.emplace_back(x);
		int idx = 0, jdx = 0;
		while (vecE[idx] != x) idx++;
		while (vecE[jdx] != 9) jdx++;
		swap(vecE[idx], vecE[jdx]);
	}

	while (!ans.empty()) {
		cout << ans.back() << '\n';
		ans.pop_back();
	}
}