[baekjoon] 11729 - 하노이 탑 이동순서(Java)

 

하노이 탑 이동순서

 

 

 

단계별로 풀어보기 10단계 재귀에 나오는 문제로 재귀로 풀어보자

접근법
제일 큰 원판이 우리가 목표로 하는 3번 장대(to)에 들어가야 순서대로 쌓을 수 있다. 그러기 위해서는 제일 큰 원판의 위에 있는 원판들을 2번 장대(remains)에 올려놓고 제일 큰 원판을 3번 장대에 옮겨야 한다.

케이스	1번장대(from)	2번장대(remains)	3번장대(to)
원판 1개	0개	0개	제일 큰 원판
원판 2개	0개	1개	제일 큰 원판
원판 3개	0개	2개	제일 큰 원판
...	...	...	...
원판 N개	0개	n-1개	제일 큰 원판

이 이후에 다시 2번 장대에 있는 n - 1개의 원판들을 3번장대로 옮겨주면 된다.

원판을 옮기는 총 횟수

케이스	횟수
원판 1개	1번
원판 2개	제일 큰 원판 위에 있는 나머지 원판 개수 : 1개 1개를 2번 장대로 옮겨놓는다 (1번) 제일 큰 원판을 3번 장대로 옮긴다 (1번) 2번 장대에 있는 원판을 3번 장대로 옮긴다 (1번)
원판 3개	제일 큰 원판 위에 있는 나머지 원판 개수 : 2개 2개를 2번 장대로 옮겨놓는다 (원판 2개 옮기는 횟수) 제일 큰 원판을 3번 장대로 옮긴다 (1번) 2번 장대에 있는 원판을 3번 장대로 옮긴다(원판 2개 옮기는 횟수)
...	...
원판 N개	제일 큰 원판 위에 있는 나머지 원판 개수 : N - 1개 N - 1 개를 2번 장대로 옮겨놓는다 (원판 N - 1개 옮기는 횟수) 제일 큰 원판을 3번 장대로 옮긴다 (1번) 2번 장대에 있는 원판을 3번 장대로 옮긴다 (원판 N - 1개 옮기는 횟수)

 

원판옮기는횟수[N] = 원판옮기는횟수[N - 1] + 1 + 원판옮기는횟수[N - 1] 이다.

원판옮기는횟수[N] = 2 * 원판옮기는횟수[N - 1] + 1​

원판을 옮기는 방법

static void moveDisc(int from, int to, int remains, int number) {
    if (number == 0) {
        return;
    }
    moveDisc(from, remains, to, number - 1); // 제일 큰 원판을 빼고 나머지 장대로 옮김
    poll[to].push(poll[from].pop()); // 제일 큰 원판을 옮김
    moveDisc(remains, to, from, number - 1); // 나머지 장대에 있던걸 목표지점으로 옮김
}

from : from 장대에서 원판을 옮길 것이다.
to : to 장대로 원판을 옮길 것이다.
remains : 두 장대 말고 남은 장대를 뜻한다.
number : 옮겨야하는 원판의 개수를 뜻한다.
poll : 크기가 4인 스택 배열이다. poll[1], poll[2], poll[3]을 장대로 사용한다.