BOJ 1914 - 하노이 탑

하노이 탑 - 🥈 Silver 1

• 문제 링크
  https://www.acmicpc.net/problem/1914

하노이의 탑 문제를 해결할 수 있는 알고리즘만 알면 쉽게 풀리는 문제다. 차근차근 접근해보지 않아 처음에는 해당 알고리즘을 떠올리기가 어려웠다.

하노이의 탑에는 총 3개의 막대가 존재한다. 1번째 막대에 순서대로 놓여있는 원판을 3번째 막대로 전부 옮기는 것이 목표이다. 원판은 한개씩만 옮길 수 있으며, 큰 원판이 작은 원판 위로 올 수 없다.

앞으로 설명의 편의를 위하여 가장 작은 원판부터 순서대로 1, 2... 번 원판으로 칭하겠다.

원판이 1개밖에 없을 경우를 생각해보자. 1번째 막대에서 3번째 막대로 옮기면 종료되며, 이 경우에 드는 이동 횟수는 1회이다.

원판이 2개인 경우는 1번 원판을 2번 막대로 옮긴 이후, 가장 큰 2번 원판을 3번 막대로, 그리고 다시 1번 원판을 3번 막대로 옮기면 종료된다. 이 경우에 드는 이동 횟수는 3회이다.

원판이 3개인 경우, 최소 이동 횟수는 7회이며 그 과정은 아래와 같다.

• 1번 원판을 3번 막대로 이동
• 2번 원판을 2번 막대로 이동
• 1번 원판을 2번 막대로 이동
• 3번 원판을 3번 막대로 이동
• 1번 원판을 1번 막대로 이동
• 2번 원판을 3번 막대로 이동
• 1번 원판을 3번 막대로 이동

여기서 규칙성을 찾아볼 수 있다. 하노이 탑에서 N개의 원판이 있을 경우에 최소 이동 횟수는 아래와 같다.

횟수 = 2^N - 1

또한 N개의 원판이 있는 하노이 탑의 경우, 아래의 순서에 따라 원판을 옮기게 된다.

1. N-1개의 원판을 2번 막대(보조 막대라 칭함)로 이동
2. 가장 큰 원판인 N번 원판을 3번 막대(목표 막대라 칭함)로 이동
3. 2번 막대에 있는 N-1개의 원판을 다시 3번 막대로 이동

1번의 경우는 1번이 출발 막대, 3번이 목표 막대, 2번이 보조막대가 되며, 3번의 경우는 2번이 출발 막대, 3번이 목표 막대, 1번이 보조 막대가 된다. 위의 알고리즘에 따라 코드를 작성하여 풀이한 결과는 아래와 같다.

풀이 코드

#include <iostream>
#include <math.h>
#include <string>
using namespace std;

// 하노이 탑 함수
void hanoi(int N, int from, int to, int temp) {
	// 원판이 하나만 있을 경우에는 바로 목표 막대로 이동
	if (N == 1) {
		cout << from << " " << to << "\n";
		return;
	}
    // 아닐 경우에는 위의 알고리즘에 따라 이동
	else {
		hanoi(N - 1, from, temp, to);
		cout << from << " " << to << "\n";
		hanoi(N - 1, temp, to, from);
	}
}

int main() {
	int N;
	cin >> N;
    // 범위가 long long int를 넘어가므로, string으로 저장
	string a = to_string(pow(2, N));
    // 소숫점 아래 부분은 출력하지 않도록 위치를 찾음
	int x = a.find('.');
    // 찾은 위치를 바탕으로 소숫점 윗 부분만 저장
	a = a.substr(0, x);
	a[a.length() - 1] -= 1;
    // 결과 출력
	cout << a << "\n";
	if (N <= 20) {
		hanoi(N, 1, 3, 2);
	}
}

결과

알고리즘은 이상이 없었으나 입력값에 따른 출력값의 범위를 생각해주지 않아 이 부분에서 시행착오가 있었다. 이후에 long long int 를 넘어서는 Big int 에 대해서 학습할 예정이다.