하노이의 탑 (재귀)

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

프로그래머스

 

문제 풀이

재귀 함수의 바이블, 하노이의 탑 문제이다. 워낙 유명한 문제라 다른 블로그에 좋은 글들이 많다.

https://mgyo.tistory.com/185

'하노이의 탑' 이해하기 (feat. 재귀 함수)

 

 

작성한 코드

import java.util.ArrayList;
import java.util.List;

class Solution {
        public int[][] solution(int n) {
        List<int[]> answer = new ArrayList<>();

        hanoi(n,1,3,2, answer);

        int[][] result = new int[answer.size()][2];

        for (int i =0; i < answer.size(); i++) {
            result[i] = answer.get(i);
        }

        return result;
    }

    public void hanoi(int n, int start, int end, int sub,  List<int[]> answer) {

    System.out.println("hanoi 함수 진입 // n:" + n + ", start: " + start + ", end: " + end + ", sub:" + sub);

        if (n == 1) {
            answer.add(new int[]{start,end});
            return;
        }
        else {
            hanoi(n-1, start, sub, end, answer);
            answer.add(new int[]{start,end});
            System.out.println("move start:" + start + " -> " + end);
            hanoi(n-1, sub, end, start, answer);
        }
        return ;
    }
}

 

 

로그

로그를 찍어서 데이터의 흐름을 보면 도움이 된다.

(n = 4 인 경우의 로그)

hanoi 함수 진입 // n:4, start: 1, end: 3, sub:2
hanoi 함수 진입 // n:3, start: 1, end: 2, sub:3
hanoi 함수 진입 // n:2, start: 1, end: 3, sub:2
hanoi 함수 진입 // n:1, start: 1, end: 2, sub:3
move start:1 -> 3
hanoi 함수 진입 // n:1, start: 2, end: 3, sub:1
move start:1 -> 2
hanoi 함수 진입 // n:2, start: 3, end: 2, sub:1
hanoi 함수 진입 // n:1, start: 3, end: 1, sub:2
move start:3 -> 2
hanoi 함수 진입 // n:1, start: 1, end: 2, sub:3
move start:1 -> 3
hanoi 함수 진입 // n:3, start: 2, end: 3, sub:1
hanoi 함수 진입 // n:2, start: 2, end: 1, sub:3
hanoi 함수 진입 // n:1, start: 2, end: 3, sub:1
move start:2 -> 1
hanoi 함수 진입 // n:1, start: 3, end: 1, sub:2
move start:2 -> 3
hanoi 함수 진입 // n:2, start: 1, end: 3, sub:2
hanoi 함수 진입 // n:1, start: 1, end: 2, sub:3
move start:1 -> 3
hanoi 함수 진입 // n:1, start: 2, end: 3, sub:1