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

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

11729번: 하노이 탑 이동 순서 (acmicpc.net)

11729번: 하노이 탑 이동 순서

유명한 재귀 문제이기도 한 하노이 탑 문제다.

 

예전에 파이썬으로 풀고 글을 업로드한 경험이 있는데, 아래에 링크를 두었다. 이때는 최소 이동 횟수를 계산했었다는 게 놀랍다. 과거의 나 대단하군.

[백준알고리즘] 11729번: 하노이 탑 이동 순서 -Python (tistory.com)

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

 

오늘은 저렇게 이동 횟수를 연산하지 않고, 바로 문제를 풀었다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

사실 예전에는 이정도 문제는 달달 외우듯이 바로 풀었는데, 오랜만에 하니까 기억이 안 났다.

 

그래서 원판이 1개일 때, 2개일 때, 3개일 때처럼 하나씩 원판의 개수를 늘리면서 직접 그려봤다. 그리고 이런저런 규칙들을 찾아보다가 드디어 찾게 되었고, 예전의 기억이 떠올랐다.

 

문제를 푸는 방법은 다른 블로그 글들에도 많이 나와있겠지만, 간단히 설명하자면 다음과 같이 분리해서 바라볼 수 있다.

1. \(N\) 개의 원판을 \(A\)에서 \(C\)로 옮기려고 한다.
2. \(N\) 번째 원판 위의 나머지 \(N-1\) 개의 원판들을 \(A\)에서 \(B\)로 옮긴다.
3. \(N\)번째 원판을 \(A\)에서 \(C\)로 옮긴다.
4. \(B\)에 위치한 \(N-1\)개의 원판들을 \(C\) 구역의 \(N\) 번째 원판 위로 옮긴다. 

 

따라서, \(N\) 개의 원판을 \(A\)에서 \(C\)로 옮기는 것은 다음과 같이 정리할 수 있고, 이는 재귀 방식을 사용하면 되는 것을 알 수 있다.

1. \(N-1\) 개의 원판을 \(A\)에서 \(B\)로 옮긴다. (재귀)
2. \(N\) 번째 원판을 \(A\)에서 \(C\)로 옮긴다.
3. \(N-1\) 개의 원판을 \(B\)에서 \(C\)로 옮긴다. (재귀)

 

위에서 2번에 해당하는 내용을 모두 queue에 넣어줌으로써 각 단계에서 원판이 어느 지점에서 어느 지점으로 이동하는 지를 파악했다. 이후, 모든 이동이 끝난 뒤에 queue의 전체 크기가 총 이동 횟수임으로 크기를 출력해주었다. 그리고 queue를 순서대로 pop 하면서 전체 이동 경로를 출력해주었다.

 

쉬운 문제에 속하는 하노이 탑인만큼 오랜만에 문제를 접해도 쉽게 예전과 같은 코드를 짤 수 있었다. 다시 다양하게 공부해야겠다.

#include <iostream>
#include <queue>

std::queue<std::pair<int, int>> g_moveQueue;

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL); 
	std::cout.tie(NULL); 
	
	solve();
}

void hanoi(int height, int current, int next, int temp)
{
	if (0 == height)
		return;

	hanoi(height - 1, current, temp, next);
	g_moveQueue.push(std::make_pair(current, next));
	hanoi(height - 1, temp, next, current);
}

void solve(void)
{
	int n;
	std::cin >> n;

	hanoi(n, 1, 3, 2);

	std::cout << g_moveQueue.size() << '\n';
	while (g_moveQueue.size())
	{
		std::pair<int, int> move = g_moveQueue.front();  g_moveQueue.pop();
		std::cout << move.first << ' ' << move.second << '\n';
	}
}