HANOI4(하노이탑)

(출처) https://algospot.com/judge/problem/read/HANOI4

4개의 기둥에 12개의 원반

해당 문제에서 입력으로 들어올 수 있는 n(원반)의 최대값은 12이다.

따라서 존재하는 4개의 기둥에 크기가 전부 다른 12개의 원반을 배치한다고 할 때, 나눠지는 총 경우의 수는 과연 몇 개 정도가 될까라는 생각에서부터 고민을 시작해보았다.

문제의 조건에 의해 크기가 작은 원반 위에 더 큰 원반을 올릴 수는 없으므로, 가장 크기가 큰 원반부터 4개의 기둥 중 하나를 골라서 넣으면서 모든 원반을 전부 배치한다고 생각한다면 경우의 수는 총 4^12개 == 16777216개가 된다.

이때 원반이 배치되어있는 모든 경우를 하나의 정점(상태)으로 바라본다면 총 1600만정도의 정점으로 구성되어 있는 그래프를 탐색하여 시작점과 종료점의 최단경로를 찾는 그래프 탐색문제로 바라볼 수 있다. (시작점은 입력으로 주어지고, 종료점은 모든 원반이 오른쪽 기둥에 올라가져있는 상태)

해당 그래프를 시작점과 종료점에서 양방향 BFS 탐색을 진행시킨다면 얼추 시간에 맞게 해결될 것 같아서 이 방향으로 문제를 풀고자 하였다.

BFS 탐색

이때 하나의 상태에서 다른 상태로 이어지는 adj 간선은, 상태별로 최소 3개에서 최대 6개를 가질 수 있다. (모든 원반의 크기가 다르고, 작은 원반은 큰 원반위에 올라갈 수 없는 조건이기때문에 하나의 원반을 다른 기둥으로 옮길 수 있는 경우는 최소 3개에서 최대 6개)

따라서 그냥 모든 상태가 6개의 인접상태를 가진다고 대충 가정해버리고 계산한다고하더라도, 입력으로 주어지는 그래프에 존재하는 최대간선은 1억개 미만이 된다.

물론 해당 문제는 시작점에서부터 탐색을 시작해 종료점을 찾게되면 바로 종료되기때문에 모든 정점과 간선을 따라가며 탐색을 할 필요가 없었고, 모든 간선이 양방향으로 연결되어 있으므로 양방향 탐색을하면 훨씬 적은 탐색계산만으로 해결할 수 있어보였다.

또한 이전 SORTGAME에서 비트마스크를 이용한 풀이를 보면서 언제 한번 해당 구현을 연습해보고 싶었는데, 딱 이 문제에서 사용할 수 있어보였다.

따라서 각 정점(상태)을 비트마스크 처리하여 64비트 정수로 표현하고, 해당 정수를 MAP의 KEY로 담아 탐색확인 여부를 가리고 시작점으로부터 거리를 계산해보기로 하였다.

코드 (시간초과- 64비트 마스크)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

using namespace std;



int get_mask(unsigned long long& mask, int index) {
	index = 15 - index;
	int ret = (mask >> (index * 4)) & 15;
	return ret;
}

void set_mask(unsigned long long& mask, int index, unsigned long long value) {
	index = 15 - index;
	value = value << (4 * index);
	mask = (mask & ~(15LL << (4 * index))) | value;
}

unsigned long long making_mask(vector<vector<int>> &state) {
	unsigned long long mask = 0;
	int count = 0;
	for (int i = 1; i < 5; i++) {
		for (int j = 0; j < state[i].size(); j++) {
			set_mask(mask, count , state[i][j]);
			count++;
		}
	}
	for (int i = 0; i < 4; i++) {
		set_mask(mask, 12 + i, state[0][i]);
	}
	return mask;
}

vector<vector<int>> rollback_mask(unsigned long long mask) {
	vector<vector<int>> ret(5);
	int index = 0;
	for (int i = 0; i < 4; i++) {
		ret[0].push_back(get_mask(mask,12 + i));
	}

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < ret[0][i]; j++) {
			ret[i + 1].push_back(get_mask(mask, index));
			index++;
		}
	}
	return ret;
}

vector<unsigned long long> get_adjacent(unsigned long long mask) {
	vector<unsigned long long> adj;
	vector<vector<int>> state = rollback_mask(mask);
	for (int i = 0; i < 4; i++) {
		if (state[i + 1].empty()) continue;
		int num = state[i + 1].back();
		for (int j = 0; j < 4; j++) {
			if (state[j + 1].empty()) {
				vector<vector<int>> adj_state = state;
				adj_state[i + 1].pop_back();
				adj_state[0][i] -= 1;
				adj_state[j + 1].push_back(num);
				adj_state[0][j] += 1;
				adj.push_back(making_mask(adj_state));
			}
			else {
				int compared_num = state[j + 1].back();
				if (num < compared_num) {
					vector<vector<int>> adj_state = state;
					adj_state[i + 1].pop_back();
					adj_state[0][i] -= 1;
					adj_state[j + 1].push_back(num);
					adj_state[0][j] += 1;
					adj.push_back(making_mask(adj_state));
				}
			}
		}
	}
	return adj;
}

int sgn(int x) {
	if (!x) return 0; return x < 0 ? -1 : 1;
}

int incr(int x) {
	return x < 0 ? x - 1 : x + 1;
}

int hanoi4(unsigned long long start, unsigned long long finish) {
	map<unsigned long long, int> m;
	queue<unsigned long long> q;
	if (start == finish) return 0;
	q.push(start);
	m[start] = 1;
	q.push(finish);
	m[finish] = -1;

	while (!q.empty()) {
		unsigned long long state = q.front();
		q.pop();
		vector<unsigned long long> adj = get_adjacent(state);
		for (int i = 0; i < adj.size(); i++) {
			map<unsigned long long, int>::iterator iter = m.find(adj[i]);
			if (iter == m.end()) {
				q.push(adj[i]);
				m[adj[i]] = incr(m[state]);
			}
			else {
				if (sgn(m[state]) != sgn(m[adj[i]])) {
					return abs(m[state]) + abs(m[adj[i]]) - 1;
				}
			}
		}
	}
	return -1;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tc;
	cin >> tc;
	while (tc--) {
		int N;
		cin >> N;
		vector<vector<int>> start_state(5);
		for (int i = 0; i < 4; i++) {
			int temp1, temp2;
			cin >> temp1;
			start_state[0].push_back(temp1);
			for (int j = 0; j < temp1; j++) {
				cin >> temp2;
				start_state[i + 1].push_back(temp2);
			}
		}
		vector<vector<int>> finish_state(5);
		finish_state[0] = vector<int> (3, 0);
		finish_state[0].push_back(N);
		for (int i = N; i > 0; i--) {
			finish_state[4].push_back(i);
		}

		int ret = hanoi4(making_mask(start_state), making_mask(finish_state));
		cout << ret << "\n";
	}
	
	return 0;
}

코드2 (시간초과2 - 32비트 마스크, 최적화 X)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <cstring>

using namespace std;

int m[(1 << 24)];
int N;
const int INF = 99999999;

int get_mask(int& mask, int index) {
	index = 11 - index;
	int ret = (mask >> (index * 2)) & 3;
	return ret;
}

void set_mask(int& mask, int index, int value) {
	index = 11 - index;
	value = value << (index * 2);
	mask = (mask & ~(3 << (index * 2))) | value;
}

int making_mask(vector<int> &state) {
	int mask = 0;
	for (int i = 0; i < state.size(); i++) {
		set_mask(mask, i, state[i]);
	}
	return mask;
}

/*
vector<int> rollback_mask(int mask) {
	vector<int> ret(N);
	for (int i = 0; i < N; i++) {
		ret[i] = get_mask(mask, i);
	}
	return ret;
}
*/
vector<int> get_adjacent(int mask) {
	vector<int> adj;
	int top[4] = { INF, INF, INF, INF };
	for (int i = N - 1; i > -1; i--) top[get_mask(mask, i)] = i;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			if (top[i] < top[j]) {
				int temp_mask = mask;
				set_mask(temp_mask, top[i], j);
				adj.push_back(temp_mask);
			}
		}
	}
	return adj;
}

int sgn(int x) {
	if (!x) return 0; return x < 0 ? -1 : 1;
}

int incr(int x) {
	return x < 0 ? x - 1 : x + 1;
}

int hanoi4(int start, int finish) {
	queue<int> q;
	if (start == finish) return 0;
	memset(m, 0, sizeof(m));
	q.push(start); m[start] = 1;
	q.push(finish); m[finish] = -1;
	
	while (!q.empty()) {
		int state = q.front();
		q.pop();
		vector<int> adj = get_adjacent(state);
		for (int i = 0; i < adj.size(); i++) {
			if (m[adj[i]] == 0) {
				q.push(adj[i]);
				m[adj[i]] = incr(m[state]);
			}
			else {
				if (sgn(m[adj[i]]) != sgn(m[state])) {
					return abs(m[adj[i]]) + abs(m[state]) - 1;
				}
			}
		}
	}
	return -1;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int tc;
	cin >> tc;
	while (tc--) {
		cin >> N;
		vector<int> start_state(N);
		for (int i = 0; i < 4; i++) {
			int temp1, temp2;
			cin >> temp1;
			for (int j = 0; j < temp1; j++) {
				cin >> temp2;
				start_state[temp2 - 1] = i;
			}
		}
		vector<int> finish_state(N, 3);
		int ret = hanoi4(making_mask(start_state), making_mask(finish_state));
		cout << ret << "\n";
	}
	
	return 0;
}

코드3

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <cstring>

using namespace std;

int m[(1 << 24)];
int N;
const int INF = 99999999;

int get_mask(int& mask, int index) {
	index = 11 - index;
	int ret = (mask >> (index * 2)) & 3;
	return ret;
}

void set_mask(int& mask, int index, int value) {
	index = 11 - index;
	value = value << (index * 2);
	mask = (mask & ~(3 << (index * 2))) | value;
}

int making_mask(vector<int> &state) {
	int mask = 0;
	for (int i = 0; i < state.size(); i++) {
		set_mask(mask, i, state[i]);
	}
	return mask;
}

/*
vector<int> rollback_mask(int mask) {
	vector<int> ret(N);
	for (int i = 0; i < N; i++) {
		ret[i] = get_mask(mask, i);
	}
	return ret;
}

vector<int> get_adjacent(int mask) {
	vector<int> adj;
	int top[4] = { INF, INF, INF, INF };
	for (int i = N - 1; i > -1; i--) top[get_mask(mask, i)] = i;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			if (top[i] < top[j]) {
				int temp_mask = mask;
				set_mask(temp_mask, top[i], j);
				adj.push_back(temp_mask);
			}
		}
	}
	return adj;
}
*/

int sgn(int x) {
	if (!x) return 0; return x < 0 ? -1 : 1;
}

int incr(int x) {
	return x < 0 ? x - 1 : x + 1;
}

int hanoi4(int start, int finish) {
	queue<int> q;
	if (start == finish) return 0;
	memset(m, 0, sizeof(m));
	q.push(start); m[start] = 1;
	q.push(finish); m[finish] = -1;
	
	while (!q.empty()) {
		int state = q.front();
		q.pop();
		int top[4] = { INF, INF, INF, INF };
		for (int i = N - 1; i > -1; i--) top[get_mask(state, i)] = i;
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if (top[i] < top[j]) {
					int adj_state = state;
					set_mask(adj_state, top[i], j);
					if (m[adj_state] == 0) {
						q.push(adj_state);
						m[adj_state] = incr(m[state]);
					}
					else if (sgn(m[adj_state]) != sgn(m[state])) return abs(m[adj_state]) + abs(m[state]) - 1;
				}
			}
		}	
	}
	return -1;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int tc;
	cin >> tc;
	while (tc--) {
		cin >> N;
		vector<int> start_state(N);
		for (int i = 0; i < 4; i++) {
			int temp1, temp2;
			cin >> temp1;
			for (int j = 0; j < temp1; j++) {
				cin >> temp2;
				start_state[temp2 - 1] = i;
			}
		}
		vector<int> finish_state(N, 3);
		int ret = hanoi4(making_mask(start_state), making_mask(finish_state));
		cout << ret << "\n";
	}
	
	return 0;
}