[백준 / BOJ] 11729번 하노이 탑 이동 순서 (C++, Python)

링크 : https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

---

문제

---

문제 풀이

재귀로 풀지 않으면 접근 방식이 참 어려울 것 같은 문제다.

 

찬찬히 생각해보면, 이동 과정을 통째로

 

i) n-1개의 원판을 2번째 장대로 옮긴다.

ii) 제일 밑에 있는 원판을 3번째 장대로 옮긴다.

iii) 2번째 장대에 있는 원판들을 3번째 장대로 옮긴다.

 

라고 요약할 수 있다. ii)번째 과정을 생각해보자. 이는

 

1) 2번째 장대의 맨 마지막 원판을 제외한 원판들을 1번째 장대에 옮긴다.

2) 2번째 장대의 맨 마지막 원판을 3번째 장대에 옮긴다.

3) 1번째 장대에 있던 원판들을 3번째 장대에 옮긴다.

 

인데, 이는 재귀적으로 구현할 수 있다. 결국 일련의 과정이 막대의 위치만 달라졌을 뿐 원래의 문제의 축소된 형태이기 때문이다.

 

 

C++ 코드 전문

	#include <iostream>
	using namespace std;
	// 순서대로 start, mid, end 장대라고 가정하자.
	// 하노이탑 과정을 통째로 생각하면, n-1개의 원판을 mid에 옮기고
	// 나머지 원판을 end로 옮기고, 다시 mid에 있는 원판들을 end에 옮기면 된다.
	void solution(int N, int start, int mid, int end) {
	if (N == 1)
	cout << start << " " << end << "\n";
	else {
	solution(N - 1, start, end, mid);
	cout << start << " " << end << "\n";
	solution(N - 1, mid, start, end);
	}
	}
	int main() {
	int N;
	cin >> N;
	cout << (1 << N) - 1 << "\n";
	solution(N, 1, 2, 3);
	return 0;
	}

view raw 11729_하노이 탑 이동 순서 (22.04.10 성공).CPP hosted with ❤ by GitHub

 

Python 코드 전문

	#include <iostream>
	using namespace std;
	// 순서대로 start, mid, end 장대라고 가정하자.
	// 하노이탑 과정을 통째로 생각하면, n-1개의 원판을 mid에 옮기고
	// 나머지 원판을 end로 옮기고, 다시 mid에 있는 원판들을 end에 옮기면 된다.
	void solution(int N, int start, int mid, int end) {
	if (N == 1)
	cout << start << " " << end << "\n";
	else {
	solution(N - 1, start, end, mid);
	cout << start << " " << end << "\n";
	solution(N - 1, mid, start, end);
	}
	}
	int main() {
	int N;
	cin >> N;
	cout << (1 << N) - 1 << "\n";
	solution(N, 1, 2, 3);
	return 0;
	}

view raw 11729_하노이 탑 이동 순서 (22.04.10 성공).CPP hosted with ❤ by GitHub

 

소감