6. BFS - 하노이의 탑(hanoi4) 문제

문제를 해결하기 위해 각 기둥에 원반이 배치되어 있는 상태를 정점으로 하는 그래프를 모델링 할 수 있다.

각 정점은 현재 상태에서 원반 하나를 조건에 맞게 옮긴 후의 상태의 정점으로 간선을 연결할 수 있다.

그러면 문제는 이 그래프에서 시작 정점에서부터 종료 정점까지의 최단 경로의 길이를 구하는 문제가 된다.

먼저, 하노이 탑의 배치 상태를 나타내는 객체를 구현해야 한다.

각 기둥에 꽂힌 원반의 번호를 정수형 배열로써 저장하는 방법이 있다.

이 때 정수형 배열은 총 4개가 필요하게 되는데, 이는 메모리가 많이 들고 객체를 복사하는데 많은 비용이 든다.

어차피 각 기둥에서 원반들은 무조건 큰 원반 위에 작은 원반이 위치하게 되기 때문에,

각 원반들이 꽂혀있는 기둥의 번호를 모두 알고있다면, 이 때 원반의 배치는 유일하게 결정된다.

따라서 각 기둥에 0번부터 3번까지 번호를 매기고, 각 원반에 몇 번 기둥에 꽂혀있는지 길이 n인 배열로 나타낼 수 있다.

이 때 각 원소를 표현하는데 2비트면 충분하므로, 비트마스크 기법을 적용하면 현재 상태를 4^n-1 범위의 정수로 나타낼 수 있다.

그러면 각 정점의 경로 길이를 저장하는 배열도 map 대신 정수형 배열을 사용할 수 있다.

위와 같이 기둥의 번호를 00부터 11까지 정하여 하나의 정수형 변수에 이진수로 나타내는 것이다.

이제 그래프에서 입력 받은 시작 정점에서 종료 정점까지의 최단 경로의 길이를 구하면 된다.

그런데 해당 그래프는 양방향 그래프이므로, 양방향 탐색을 통해 수행 시간을 단축할 수 있다.

// 하노이의 탑 문제를 해결하는 양방향 탐색 알고리즘

#include <iostream>

#include <vector>

#include <string>

#include <queue>

#include <string.h>

using namespace std;

int c[1 << (13 * 2)];

// 현재 상태에서 disc번 원반이 몇번 기둥에 있는지 리턴

int get(int state, int disc) {

return (state >> (disc * 2)) & 3;

}

// 현재 상태에서 disc번 원반을 p번 기둥으로 옮겼을 때 상태 리턴

int set(int state, int disc, int p) {

return (state & ~(3 << (disc * 2))) | (p << (disc * 2));

}

int inc(int x) {

if (x < 0) return x - 1;

else return x + 1;

}

int sign(int x) {

if (x == 0) return 0;

else if (x > 0) return 1;

else return -1;

}

int moving(int begin, int n) {

// 타워의 마지막 상태 정의

int finish = 0;

for (int i = 1; i <= n; i++) {

finish = finish | (3 << (i * 2));

}

if (begin == finish) return 0;

memset(c, 0, sizeof(c));

queue<int> q;

c[begin] = 1;

c[finish] = -1;

q.push(begin);

q.push(finish);

while (!q.empty()) {

int here = q.front();

q.pop();

// 현재 상태에서 각 기둥의 맨 위에 꽂힌 원반의 번호 계산

int top[4] = { -1,-1,-1,-1 };

for (int disc = n; disc > 0; disc--) {

top[get(here, disc)] = disc;

}

for (int i = 0; i < 4; i++) {

if (top[i] == -1) continue;

for (int j = 0; j < 4; j++) {

if (i == j) continue;

if (top[j] == -1 || top[i] < top[j]) {  // 다른 기둥으로 옮길 수 있는 경우

int there = set(here, top[i], j);

if (c[there] == 0) {  // 아직 이 상태를 발견하지 않았다면

q.push(there);

c[there] = inc(c[here]);

}

else if (sign(c[here]) != sign(c[there])) {  // 양방향 탐색이 서로 만났다면

return abs(c[here]) + abs(c[there]) - 1;

}

}

}

}

}

return -1;  // 실패했을 경우

}

int main() {

int c;  // 테스트 케이스수

vector<int> result;

cin >> c;

for (int test = 0; test < c; test++) {

int n;  // 원반의 총 수

int first = 0;  // 처음 원반이 꽂혀있는 상태

string stemp;

cin >> n;

getline(cin, stemp);

for (int k = 0; k < 4; k++) {

string input;

getline(cin, input);

char in[40];

strcpy(in, input.c_str());

char *tok = strtok(in, " ");

string temp = tok;

int num = atoi(temp.c_str());

tok = strtok(NULL, " ");

while (tok != NULL) {

temp = tok;

int disc = atoi(temp.c_str());

first = first | (k << (disc * 2));

tok = strtok(NULL, " ");

}

}

int res = moving(first, n);

result.push_back(res);

}

for (int i = 0; i < c; i++) {

cout << result[i] << endl;

}

return 0;

}