백준 11729번 : 하노이 탑 이동순서 (JAVA) 문제 풀이

www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

---

 

 

 

문제 분석

일단, 하노이 탑이란 위에 설명을 보면 알겠지만, 조건이 두가지가 있다.

• 한번에 한 원판만 옮길 수 있다.
• 아래의 원판은 항상 위에 원판보다 크다.

 

그렇다면 과연 어떻게 옮겨야 할까? 일단 원판 3개를 가지고 규칙을 살펴보자.

1번 그림

1. 일단 1번째 타워에서 3번째 타워로 3개의 원판을 옮기기 위해서는 그 위에 있는 두개의 원판을 먼저 가운데로 옮겨야 한다. ( 5번 그림 참조)

2번 그림

2. 가장 작은 원판을 세번째로 옮겼다.

3번 그림

3. 1번 타워에는 가장 큰 원판, 2번 타워에는 중간 크기 원판, 3번 타워에는 가장 작은 원판이 있다.

4번 그림

자. 이제 어떻게 됐나 살펴보자. 드디어 가장 큰 원판이 원하는 3번 타워에 갈 수 있게 됐다.

5번 그림

이로써 우리가 알 수 있는 점은, 가장 큰 원판이 3번 타워(목표 지점)에 가기 위해서는 가장 큰 원판을 제외한 나머지 두 원판이 2번 타워로 옮겨져야 이동 할 수 있게 된다! 

6번 그림

7번 그림

 

코드 구현

3개의 원판을 이동 시키기 위해서는?

move(N , 1, 3, 2);

매개변수로 원판의 개수, 현재 타워 번호, 목표 타워 번호, 서브 타워 번호 이렇게 넘겨준다.

 

아까 5번 그림에서 알게 된 가장 밑에 원판을 제외한 나머지 두개의 원판이 2번 타워로 옮겨져야만 가장 큰 원판이 목표 타워로 이동 할 수 있게 되었다.

그냥 단순하게 두개의 원판이 있다고 가정하고, 그 두개의 원판을 2번 타워에 옮겨야 한다고 생각해보자.

그렇다면 여기서 가장 큰 원판은 중간 크기의 원판이 될 것이고, 그렇다면 또 가장 큰 원판을 옮기려면 역시 나머지 원판을 2번타워가 아닌 3번 타워에 옮겨놓아야 한다. 그렇다면 아래의 그림처럼 될 것이다.

나머지 옮기는 이미지는 생략.

코드로 표현 하면,

move(N-1, 1, 2, 3);

 

이 부분을 계속 원판의 개수가 1이 될 때까지 재귀로 호출 하게 되는 것이다.  재귀로 표현 되는 식을 보면,

// start : 1, sub : 2, end : 3

move(3, start, end, sub);

->	move(2, start, sub, end);
     ->	move(1, start, end, sub);
        print(start + " -> " + sub);
     -> move(1, end, sub, start);
        
    print(start + " -> " + end);
    
->    move(2, sub, end, start);
     ->	move(1, start, end, sub);
        print(start + " -> " + end);
     -> move(1, end, sub, start);

 

전체 코드

public class Main {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        
        move(N, 1, 3, 2); // 3개의 원판을 1번타워에서 3번 타워로 옮기고 2번 타워는 서브로 사용.
    }

	private static void move(int N, int start, int end, int sub) {
    	if( N==1 ) {
        	System.out.println(start + " -> " + end);
            return ;
        }
        
        move(N-1, start, sub, end); // N-1개를 목표 지점이 아닌 타워에다가 옮겨 놔야 가장 큰 원판을 옮길 수 있겠죠?
        	move(1, start, end, sub); // 위에 move 메소드가 끝나면, sub에 나머지 원판이 쌓여있고, 3번 타워에는 비워있게 되어서 바로 큰 원판을 옮기면 된다.
        move(N-1, sub, end, start); // 아까 옮겨 놓았던 원판을 다시 sub -> end 타워로 옮기는 호출을 한다.
    }
}