[백준] 11729번 하노이 탑 이동 순서

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

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

 

출력

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

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

 

 

이 문제는 객체지향 적 사고로 풀면 절대 안되는 문제라고 한다. 그냥 그려러니 하고 넘어가야 된다고 한다.

 

#include <bits/stdc++.h>
using namespace std;

void go(int a, int b, int n) {
  if (n == 0) {
    return;
  }

  go(a,6-a-b,n-1);
  cout << a << ' ' << b << '\n';
  go(6-a-b,b,n-1);
}

int main(void) {    
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL);

  int n;
  cin >> n;

  cout << (1<<n) -1 << "\n";
  go(1,3,n);
  
}
 

 

하노이 탑 규칙을 보면

 

무조건 큰거 위에는 작은게 올라간다는 규칙이 있다.

이것으로 미뤄 봤을때

1첫번째에 가있다면 2번째 혹은 3번째로 옮겨야 된다. 하지만 최종적으로 3번째 막대기에 있어야한다.

그렇기 때문에 첫번째 원판은 무조건 3번째로 옮겨야 한다.

왜냐하면 2번째에 옮기게 되면 두 번째로 작은 원판을 옮겼을때 세번째 막대기로 모이게 되기 때문이다.

이를 방지하기 위해 무조건 가장 작은것은 세번째 막대기로 옮겨야 된다.

 

이것을 미뤄 봣을때

6-a-b같은 경우를 보면 2번째로 옮겨진다.

그러니까 1,3 이 되겠고...

 

 

뭐 이런식으로 계속하다보면

 1 3

 1 2

 3 2

 1 3

 2 1

 2 3

 1 3

으로 원판이 옮겨 진다.

 

이를 해석 해보면 첫번째 원판은 3번째로

                       두번째 원판은 2번째로

                       첫번째 원판은 다시 2번째로 그러면 1 / 2 가 된다.

                       그러면 세번째 원판을 3번째로

                       첫번째 원판을 1 번째로 

                        두번째 원판을 2번째로

                        이제 마지막으로 첫번째 원판을 3번째 막대기로 옮기면 끝이다.

     

   뭐 이런식으로 동작한다. 다시 문제를 풀어야 봐야 되겠지만...

아마 6을 뺴는 이유는 막대기가 3개 뿐이라 그런것 같다.

 

자 마지막으로 1<<n은 비트 마스크이다.아직 비트마스크를 완벽하게 모르지만

1을 밀면 3이 8이 된다고 한다. 그걸 1뺸 값이라고 한다..

나중에... 나중에... 힉습해야지.. 

 

#include <iostream>
using namespace std;
void hanoi(int n, int start, int to, int bypass)
{
	if (n == 1)
		cout << start << ' ' << to << '\n';
	else
	{
		hanoi(n - 1, start, bypass, to);
		cout << start << ' ' << to << '\n';
		hanoi(n - 1, bypass, to, start);
	}
}
int main() {
	int num;
	cin >> num;
	cout << (1 << num) - 1 << "\n";
	hanoi(num, 1, 3, 2);
}

 

이게 더 직관적이다.