하노이의 탑

https://school.programmers.co.kr/learn/courses/30/lessons/12946#

프로그래머스

 

재귀를 이용해서 풀어야 하는데, 일단 하노이의 탑을 해결하는 방법을 알아야 한다.

 

아래의 플래시 게임이 무척 도움되었다. 직접 원판을 옮겨볼 수 있어 풀이의 원리를 이해하는데 큰 도움이 되었다.

 

https://vidkidz.tistory.com/649

하노이의 탑 (Tower of Hanoi)

 

일단 코드를 떠나서,

 

하노이의 탑 풀이의 요지는

 

n번째 원판을 목표 기둥으로 옮기기 위해서는

 

1. n-1 번째의 원판을 보조 기둥으로 옮기고

2. n번째 원판을 목표 기둥으로 옮기고

3. 보조 기둥에 옮겼던 n-1번째의 원판을 목표 기둥으로 옮기는 것

 

이다.

 

플래시 게임을 예로 들어, TOWER 1, TOWER 2, TOWER 3을 각각 T1, T2, T3 라 칭하고, 디스크 3개를 옮긴다고 가정했을 때,

 

3번째 원판을 목표 기둥(T3)으로 옮기려면

 

우선, 2번째 원판을 보조 기둥(T2)으로 옮겨야 한다. .....(1)

 

그런데 2번째 원판 위에 첫번째 원판이 있으므로,

 

2번째 원판을 목표 기둥(T2)으로 옮기려면

 

1번째 원판을 보조 기둥(T3)으로 옮겨야 한다.

그리고 2번재 원판을 목표 기둥(T3)으로 옮기고

1번째 원판을 목표 기둥(T2)으로 옮긴다.

 

이렇게 되면 위의 (1)번 항목(2번째 원판을 보조기둥 T2로 옮겨야함)이 진행된것이므로,

 

3번째 원판을 목표 기둥(T3)으로 옮기고,

 

2번째 원판을 목표 기둥(T3)으로 옮겨야 하는데...!

 

1번째 원판을 보조 기둥(T1)으로 옮기고,

2번째 원판을 목표 기둥(T3)으로 옮기고,

1번째 원판을 목표 기둥(T3)으로 옮겨야 한다...

 

위의 요지에서 설명한걸 코드로 옮겨보면,

 

/**
diskNumber : 디스크 번호
from : 출발 기둥
sub : 보조 기둥
to : 목표 기둥
*/
void move(int diskNumber, int from, int sub, int to) {
	if (diskNumber == 1) {
    	// 이동함
        System.out.printf("[DISK : %d] %d -> %d\n", diskNumber, from, to);
    } else {
    	// n-1번째를 보조 기둥으로 옮기고,
        move(diskNumber - 1, from, to, sub);	// 여기서 기존의 보조 기둥이었던 sub가 n - 1번째 디스크의 목표 기둥이 되고, 기존의 목표 기둥이 n -1 번째 디스크의 보조 기둥이 된다.
        // n 번째를 목표 기둥으로 옮기고,
        System.out.printf("[DISK : %d] %d -> %d\n", diskNumber, from, to);
        // n-1번째를 목표 기둥으로 옮긴다.
        move(diskNumber - 1, sub, from, to);	// n - 1번째 디스크가 현재 보조 기둥에 가 있으므로, sub가 from이 되고, 기존의 from이 sub가 된다.
    }
}

 

  

이렇게 된다.

 

위에서 설명하진 않았지만, 당연히 디스크가 1번이면 목표 했던 기둥으로 바로 옮겨갈 수 있으므로 if로 체크한다.

 

아무튼,

 

프로그래머스에서는 원판 이동 경로를 배열로 나타내야 하므로, print 대신 아래 소스로 작성했다.

 

import java.util.*;

class Solution {
    
    private List<int[]> answer = new ArrayList();
    
    public int[][] solution(int n) {
        
        move(n, 1, 2, 3);
        
        return answer.stream().toArray(int[][]::new);
        
    }
    
    public void move(int disk, int from, int sub, int to) {
        if (disk == 1) {
            answer.add(new int[] {from, to});
        } else {
            move(disk - 1, from, to, sub);
            answer.add(new int[] {from, to});
            move(disk - 1, sub, from, to);
        } 
    }
    
}