BOJ 27526 슬라이딩 퍼즐 마스터

문제 링크입니다.

2-퍼즐

1×2 크기의 퍼즐이 주어졌다고 해봅시다. 한 칸에는 1이 적힌 조각이 들어 있고 다른 칸은 비어 있습니다. 우리는 빈 칸으로 1이 적힌 조각을 미는 행위밖에 할 수 없습니다.

이번에는 같은 크기의 퍼즐이지만, 두 칸에 모두 조각이 들어있는 경우를 생각해 봅시다. 우리가 할 수 있는 시행은 두 조각의 위치를 서로 바꾸는 것뿐입니다.

생각해 보면, 처음의 빈 칸이 있는 경우도 빈 칸에 2를 할당하면 1번과 2번 조각을 서로 교환하는 것과 다르지 않습니다. 따라서 우리는 빈 칸까지도 조각이 있는 것으로 생각해, 모든 시행을 인접한 두 조각의 교환으로만 생각해도 좋습니다.

어려운 케이스 찾고 변형하기

입력으로 주어질 수 있는 모든 경우를 풀려면 1×N의 경우를 풀 수 있어야 합니다. 다른 형태의 퍼즐은 ㄹ자 모양으로 따라가면서 1×N인 것처럼 생각할 수 있으니, 이 경우를 해결하는 것만으로 충분합니다.

이제 문제를 길이 N의 순열들을 인접한 수끼리 서로 바꾸는 연산을 이용해 모두 정확히 한 번씩만 방문하는 문제로 환원할 수 있습니다.

슬라이딩 퍼즐 마스터하기

1×2의 경우부터 풀이를 확장해 나갑시다. 1 2 에서 2 1 로 바꾸면 끝입니다. 여기에 3 을 추가하고 생각해 봅시다.

길이 3의 순열의 구성을 생각해 보면, 길이 2의 모든 순열마다 가능한 모든 자리에 3을 넣으면 모든 길이 3의 순열이 한 번씩 얻어집니다. 이를 이용해, 처음에 1 2 3 에서 1 3 2 , 3 1 2 로 3을 한 칸씩 왼쪽으로 밀어줍니다. 그러고서 1 과 2 를 서로 바꿔 다른 길이 2의 순열을 만들어주고, 이 상황에서 다시 3 2 1 부터 2 3 1 , 2 1 3 으로 3을 오른쪽으로 밀어주면 길이 3의 모든 순열을 얻을 수 있습니다.

이를 일반화시켜 확장하면 1×N 크기의 퍼즐이 주어졌을 때의 문제를 해결할 수 있으니, 자연스레 문제를 해결할 수 있습니다.

이 문서에 요 문제를 풀기 위한 알고리즘이 서술되어 있는데요. 뭔가 거창한 이름을 달고 있지만 내용은 전술한 알고리즘과 동일합니다.

코드

#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int>> v, last;
char c[10];

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	cin >> n >> m;
	for(int y = 0; y < n; y++){
		for(int x = 1; x <= m; x++){
			if(y&1){
				if(y*m+x == n*m) c[y*m+m+1-x] = '#';
				else c[y*m+m+1-x] = char(y*m+x+'0');
			}
			else{
				if(y*m+x == n*m) c[y*m+x] = '#';
				else c[y*m+x] = char(y*m+x+'0');
			}
		}
	}
	v.push_back({1});
	last.push_back({1});
	for(int i = 2; i <= n*m; i++){
		v.clear();
		for(int k = 0; k < last.size(); k++){
			if(k&1){
				last[k].insert(last[k].begin(), i);
				v.push_back(last[k]);
				for(int j = 1; j < last[k].size(); j++){
					swap(last[k][j-1], last[k][j]);
					v.push_back(last[k]);
				}
			}
			else{
				last[k].push_back(i);
				v.push_back(last[k]);
				for(int j = last[k].size()-1; j; j--){
					swap(last[k][j-1], last[k][j]);
					v.push_back(last[k]);
				}
			}
		}
		last = v;
	}
	for(auto i : v){
		for(int y = 0; y < n; y++){
			if(y&1) for(int x = m-1; x >= 0; x--) cout << c[i[y*m+x]];
			else for(int x = 0; x < m; x++) cout << c[i[y*m+x]];
			cout << '\n';
		}
	}
}