Algorithm/문제풀이

백준 11729 하노이 탑 이동 순서

sang_hoony 2020. 1. 10. 09:50

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

 

11729번: 하노이 탑 이동 순서

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

www.acmicpc.net

재귀 문제 예제로 정말 많이 쓰이는 문제이다. 설명을 할 때

 

start mid end 이런식으로 세부분으로 나누어서 설명하겠다. 

 

이 문제는 크게 네 분류로 나누어서 생각하면된다.

  1. 최종적으로 옮겨야하는 마지막 한개를 제외하고 start에서 end를 거쳐 mid로 옮긴다. 
  2. 마지막 남은 한개를 start에서 end부분 최종 목표로 옮긴다. 
  3. 1번에서 옮긴 나머지 조각 들을 mid에서 start를 거쳐 다시 end로 옮긴다. 
  4. 예외적으로 옮겨야할 조각이 1개 남았다면 start에서 end로 옮기면 된다. 

이 네 부분을 재귀코드로 잘 작성하면된다. 

example) start에 쌓인 조각이 3개일 때 

이 네 가지 규칙은 start에 조각이 4개든 5개든 6개든 상관없이 모두 적용이 되므로 아래와 같이 코드를 작성하면된다. 

 

더보기 
#include <stdio.h>
#include <math.h>
void hanoi(int N, int start, int mid, int end);

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

void hanoi(int N, int start, int mid, int end){
	if(N == 1)
		printf("%d %d\n",start, end);
	else{
		hanoi(N-1, start, end, mid);
		printf("%d %d\n", start, end);	
		hanoi(N-1, mid, start, end);
	}
}