[백준 11729번: 하노이 탑 이동 순서] 자바/C 언어 문제풀이

재귀함수 문제 중 유명한 하노이 탑 이동순서를 풀어보았다.

 

우선 원판 이동의 최소 횟수 값을 출력해야한다. 해결 방법은 두 가지가 있다.

 

1. 재귀함수로 (n-1)*2+1 값을 return 한다.

참고로 (n-1)*2+1 값이 최소 횟수는 아니다. 여기서 말하는 (n-1)은 n-1개의 원판을 옮기는 최소 횟수를 말한다.

따라서 (n-1)의 횟수를 구하려면 재귀함수를 이용해야한다.

참고영상 : https://youtu.be/Xu5GC_7YIeQ

유튜브의 하노이 탑 설명 영상을 참고했다. 하노이탑의 일반항 구하는 과정을 찾아보면 쉽게 알 수 있다.

간단히 원판 3개가 있다고 가정하면

1) 1~(n-1)의 원판을 B로 먼저 옮긴다.

2) n 원판을 C로 옮긴다.

3) 1~(n-1)의 원판을 다시 C로 옮긴다.

이 큰 틀을 이용하여 재귀함수를 작성할 수 있다.

 

2. 위의 1번을 이용하여 하노이 탑의 일반항을 계산하면 2^n-1이라는 공식이 나온다.

 

[C언어 풀이]

#include<stdio.h>
int Min(int N){
    if(N==1) return 1;
    return Min(N-1)*2+1;
}
void HanoiRoute(int N,int first,int mid,int end){
    if(N==1){
        printf("%d %d\n",first,end);
        return;
    }
    HanoiRoute(N-1,first,end,mid);
    printf("%d %d\n",first,end);
    HanoiRoute(N-1,mid,first,end);
}
int main(){
    int N;
    scanf("%d",&N);
    
    printf("%d\n",Min(N));
    HanoiRoute(N,1,2,3);
}

[자바 풀이]

import java.util.Scanner;
import java.io.*;
public class Main{
	public static StringBuilder show = new StringBuilder();
	int Min(int num) {
		if(num==1)return 1;
		return Min(num-1)*2+1;
	}

	void HanoiRoute(int num,int first,int mid,int end) {
		if(num==1) {
			show.append(first+" "+end+"\n");
			return;
		}
		HanoiRoute(num-1,first,end,mid);
		show.append(first+" "+end+"\n");
		HanoiRoute(num-1,mid,first,end);
		
	}
	public static void main(String[] args) throws IOException {
		Scanner scanner = new Scanner(System.in);
		Main test = new Main();
		int num = scanner.nextInt();
		
		System.out.println(test.Min(num));
		test.HanoiRoute(num,1,2,3);
		System.out.println(show);
		
	}
}

 

* 참고로 백준에서 자바로 제출할 때는 유의사항이 있다.

1. public class의 이름은 Main이어야한다.

2. 컴파일 에러는 없지만 시간초과가 뜨는 경우가 있다.

1) scanner가 시간이 좀 오래걸린다고 한다. 이럴 경우 BufferedReader를 이용해야한다.

2) System.out.println 을 사용할 때 재귀함수에서 사용할 경우 시간초과가 뜰 수 있다.

그럴 경우 위의 예시처럼 StringBuilder를 이용해야한다.

처음에 유의사항을 몰라서 당황했다...백준 풀 때는 자바말고 다른 언어로 풀까 고민 중이다ㅎ