[C++ 알고리즘] 백준 11729번 : 하노이 탑 이동 순서

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
1. 한 번에 한개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

풀이 과정

부르기 쉽게 기둥 이름을 가장 왼쪽부터 1,2,3이라고 가정을 해보자. 1번에 있는 맨 밑에 있는 가장 큰 원판을 목적지인 3번 기둥을 맨 밑으로 깔아야 한다.

그러기 위해서는 1번 기둥에 있는 n개의 원판 중 가장 아래 있는 1개의 원판을 제외한 n-1개의 원판을 2번 기둥으로 옮겨야된다.

n-1개의 원판을 2번 기둥에 옮기는 과정도 위와 같이 진행하면 된다. 2번 기둥의 맨 밑에 n-1개의 원판 중 가장 큰 원판이 밑으로 가야 하고 나머지 n-2개의 원판은 3번의 기둥을 이용하여 이동되어야 한다.

우선 최단경로를 만들기 위한 재귀 함수 만들기

void Hanoi(int n, int a, int b, int c) {
	if (n == 1) {
		printf("%d %d\n", a, c);
		return;
	}
	else {
		Hanoi(n - 1, a, c, b);
		printf("%d %d\n", a,c );
		Hanoi(n - 1, b, a, c);
	}
}

우선 재귀 함수를 만들 때

if (n == 1) {
		printf("%d %d\n", a, c);
		return;
}

Hanoi 함수의 탈출 조건으로 Base case를 만들어 준다. 결국에 하노이 원판을 다 옮기는 조건은 마지막 원판의 개수가 1일때 마지막 기둥으로 옮긴다.

else {
		Hanoi(n - 1, a, c, b);
		printf("%d %d\n", a,c );
		Hanoi(n - 1, b, a, c);
}

a를 1번 기둥
b를 2번 기둥
c를 3번 기둥이라고 이해 한다면 코드 순서대로
기둥1의 n-1개의 원판을 기둥2로 옮기는 과정이고
그다음 기둥1의 1개 원판을 기둥 3으로 옮기는 출력
마지막으로 기둥 2의 n-1개의 원판을 다시 기둥3으로 옮기는 과정이다.

이 과정들을 완료 하였다면 main 함수로 넘어가자.

int main() {
	int N;
	scanf("%d", &N);
	printf("%d\n", (int)pow(2,N)-1);
	Hanoi(N, 1, 2, 3);
	
	return 0;
}

문제에 원하는 출력은 최단 경로로 이동하였을 때의 경우의 수 다음 이동 경로들을 출력하는 것이므로 pow함수를 사용함으로써 경우의 수와 Hanoi함수를 사용하여 답을 출력한다.

코드

#pragma warning(disable : 4996)

#include <stdio.h>
#include <iostream>
#include <cmath>

using namespace std;


void Hanoi(int n, int a, int b, int c) {
	if (n == 1) {
		printf("%d %d\n", a, c);
		return;
	}
	else {
		Hanoi(n - 1, a, c, b);
		printf("%d %d\n", a,c );
		Hanoi(n - 1, b, a, c);
	}

}

int main() {
	int N;
	scanf("%d", &N);
	printf("%d\n", (int)pow(2,N)-1);
	Hanoi(N, 1, 2, 3);
	
	return 0;
}

결과

여기서 include <cmath>를 쓰지 않고 컴파일하느라 에러가 떴다. 한동안 알아채느라 시간이 조금 걸렸다.