취미로 코딩하기

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

이번에 볼 문제는 백준 2701번 문제인 육각 퍼즐이다.
문제는 아래 링크를 확인하자.

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

퍼즐의 각 칸에 동전이 놓여있는 7!가지의 각 경우를 노드로, 한 번의 움직임으로 서로간에 바뀔 수 있는 두 상태 사이에 에지를 그은 그래프로 문제의 상황을 모델링해보자. 이 때, 이 문제의 해답은 각 상태와 초기상태 사이의 최단거리를 구하는 문제의 답과 같게 된다.

위의 모델링에서 초기상태를 나타내는 노드를 출발 노드로 해 BFS를 돌려 각 상태와의 최단거리를 미리 전부 구해두는 것으로 문제를 해결할 수 있다. 초기상태에서 접근할 수 없는 상태는 -1을 출력하자.

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

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

struct puzzle {
	char a, b, c, d, e, f, x;
	puzzle() {};
	puzzle(char A, char B, char C, char D, char E, char F, char X) {
		a = A, b = B, c = C, d = D, e = E, f = F, x = X;
	}
	bool operator== (const puzzle& p) {
		return a == p.a && b == p.b && c == p.c && d == p.d && e == p.e && f == p.f;
	}
	bool operator< (const puzzle& p) const {
		if (a != p.a) return a < p.a;
		if (b != p.b) return b < p.b;
		if (c != p.c) return c < p.c;
		if (d != p.d) return d < p.d;
		if (e != p.e) return e < p.e;
		if (f != p.f) return f < p.f;
		return x < p.x;
	}
};

map<puzzle, pair<puzzle, char>> mp;

void init() {
	mp.insert(make_pair(puzzle('A', 'B', 'C', 'D', 'E', 'F', 'X'), make_pair(puzzle('A', 'B', 'C', 'D', 'E', 'F', 'X'), 'X')));
	queue<puzzle> que;
	que.push(puzzle('A', 'B', 'C', 'D', 'E', 'F', 'X'));
	while (!que.empty()) {
		puzzle cur = que.front(); que.pop();
		puzzle nxt = cur;
		if (cur.a == 'X') {
			swap(nxt.a, nxt.f);
			if (mp.find(nxt) == mp.end()) {
				mp.insert(make_pair(nxt, make_pair(cur, cur.f)));
				que.push(nxt);
			}
			swap(nxt.a, nxt.f);
			swap(nxt.a, nxt.b);
			if (mp.find(nxt) == mp.end()) {
				mp.insert(make_pair(nxt, make_pair(cur, cur.b)));
				que.push(nxt);
			}
			swap(nxt.a, nxt.b);
		}
		else if (cur.b == 'X') {
			swap(nxt.b, nxt.a);
			if (mp.find(nxt) == mp.end()) {
				mp.insert(make_pair(nxt, make_pair(cur, cur.a)));
				que.push(nxt);
			}
			swap(nxt.b, nxt.a);
			swap(nxt.b, nxt.x);
			if (mp.find(nxt) == mp.end()) {
				mp.insert(make_pair(nxt, make_pair(cur, cur.x)));
				que.push(nxt);
			}
			swap(nxt.b, nxt.x);
			swap(nxt.b, nxt.c);
			if (mp.find(nxt) == mp.end()) {
				mp.insert(make_pair(nxt, make_pair(cur, cur.c)));
				que.push(nxt);
			}
			swap(nxt.b, nxt.c);
		}
		else if (cur.c == 'X') {
			swap(nxt.c, nxt.b);
			if (mp.find(nxt) == mp.end()) {
				mp.insert(make_pair(nxt, make_pair(cur, cur.b)));
				que.push(nxt);
			}
			swap(nxt.c, nxt.b);
			swap(nxt.c, nxt.d);
			if (mp.find(nxt) == mp.end()) {
				mp.insert(make_pair(nxt, make_pair(cur, cur.d)));
				que.push(nxt);
			}
			swap(nxt.c, nxt.d);
		}
		else if (cur.d == 'X') {
			swap(nxt.d, nxt.c);
			if (mp.find(nxt) == mp.end()) {
				mp.insert(make_pair(nxt, make_pair(cur, cur.c)));
				que.push(nxt);
			}
			swap(nxt.d, nxt.c);
			swap(nxt.d, nxt.e);
			if (mp.find(nxt) == mp.end()) {
				mp.insert(make_pair(nxt, make_pair(cur, cur.e)));
				que.push(nxt);
			}
			swap(nxt.d, nxt.e);
		}
		else if (cur.e == 'X') {
			swap(nxt.e, nxt.d);
			if (mp.find(nxt) == mp.end()) {
				mp.insert(make_pair(nxt, make_pair(cur, cur.d)));
				que.push(nxt);
			}
			swap(nxt.e, nxt.d);
			swap(nxt.e, nxt.x);
			if (mp.find(nxt) == mp.end()) {
				mp.insert(make_pair(nxt, make_pair(cur, cur.x)));
				que.push(nxt);
			}
			swap(nxt.e, nxt.x);
			swap(nxt.e, nxt.f);
			if (mp.find(nxt) == mp.end()) {
				mp.insert(make_pair(nxt, make_pair(cur, cur.f)));
				que.push(nxt);
			}
			swap(nxt.e, nxt.f);
		}
		else if (cur.f == 'X') {
			swap(nxt.f, nxt.e);
			if (mp.find(nxt) == mp.end()) {
				mp.insert(make_pair(nxt, make_pair(cur, cur.e)));
				que.push(nxt);
			}
			swap(nxt.f, nxt.e);
			swap(nxt.f, nxt.a);
			if (mp.find(nxt) == mp.end()) {
				mp.insert(make_pair(nxt, make_pair(cur, cur.a)));
				que.push(nxt);
			}
			swap(nxt.f, nxt.a);
		}
		else {
			swap(nxt.x, nxt.b);
			if (mp.find(nxt) == mp.end()) {
				mp.insert(make_pair(nxt, make_pair(cur, cur.b)));
				que.push(nxt);
			}
			swap(nxt.x, nxt.b);
			swap(nxt.x, nxt.e);
			if (mp.find(nxt) == mp.end()) {
				mp.insert(make_pair(nxt, make_pair(cur, cur.e)));
				que.push(nxt);
			}
			swap(nxt.x, nxt.e);
		}
	}
}

puzzle puz0 = puzzle('A', 'B', 'C', 'D', 'E', 'F', 'X');

void solve() {
	string s; cin >> s;
	puzzle puz = puzzle(s[0], s[1], s[2], s[3], s[4], s[5], 'X');
	if (mp.find(puz) == mp.end()) cout << -1 << '\n';
	else {
		string ans = "";
		while (!(puz == puz0)) {
			auto& tmp = mp[puz];
			puz = tmp.first, ans += tmp.second;
		}
		cout << ans.size() << ' ' << ans << '\n';
	}
}

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

	init();
	int T; cin >> T;
	while (T--) solve();
}