[Programmers] 하노이의 탑

문제

"하노이의 탑" 문제에서 '원판 옮기는 패턴'을 반환해야 하는 문제였다.

해석

n이 15일 때, 그 옮기는 연산의 개수는 32,767정도이다. 따라서 하노이의 탑 문제의 패턴을 알고 있다면 단순 완탐을 하여도 무방할 것으로 예상할 수 있다.

풀이

자바를 이용하여 최대한 빠르게 로직을 구성했다. ('최대한 빠르게'라는 말의 의미는, 최적화를 고려하지 않고 바로 떠오르는대로 로직을 구성함을 의미한다.)

import java.util.*;

class Solution {
    public int[][] solution(int n) {
        int[][] answer = {};
        
        if (n == 1) {
            return new int[][]{{1,3}};
        } else if (n == 2) {
            return new int[][]{{1,2},{1,3},{2,3}};
        } else {
            answer = go(n);
        }
        
        
        return answer;
    }
    
    public int[][] go(int i) {
        int[][] tmp = new int[][]{{1,2},{1,3},{2,3}};
        List<int[]> next = new ArrayList<>();
        for (int j = 2; j < i; j++) {
            next.clear();
            for (int k = 0; k < tmp.length; k++) {
                int[] t = tmp[k].clone();
                System.out.println(t[0] + " " + t[1]);
                if (t[0] == 2) {
                    t[0] = 3;
                } else if (t[0] == 3) {
                    t[0] = 2;
                }
                if (t[1] == 2) {
                    t[1] = 3;
                } else if (t[1] == 3) {
                    t[1] = 2;
                }
                next.add(t);
            }            
            next.add(new int[]{1,3});
            for (int k = 0; k < tmp.length; k++) {
                int[] t = tmp[k].clone();
                if (t[0] == 1) {
                    t[0] = 2;
                } else if (t[0] == 2) {
                    t[0] = 1;
                }
                if (t[1] == 1) {
                    t[1] = 2;
                } else if (t[1] == 2) {
                    t[1] = 1;
                }
                next.add(t);
            }
   
            tmp = new int[next.size()][2];
            for (int k = 0; k < next.size(); k++) {
                tmp[k] = next.get(k);
            }
        }
        
        return tmp;
    }

}

말 그대로 반복문을 이용하여 단순하게 구현하면 위와 같이 풀 수 있다. 하지만 딱 보면 코드 중복이 발생하고 있으므로, 똑똑한 사람들은 재귀를 사용하여 더욱 명료하게 풀 수 있을 것이다. 명료하게 푸는 방법은 파이썬으로 풀어봤다.

def solution(n):
    return go(n, 1, 3)

def go(depth, start, end):
    res = []
    mid = 6 - start - end
    
    if depth == 1:
        res += [[start, end]]
        return res
    else:
        res += go(depth-1, start, mid)
        res += [[start, end]]
        res += go(depth-1, mid, end)
        return res