[프로그래머스] 하노이의 탑 | 재귀 호출 | 분할 정복

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

다시 알고리즘 문제를 풀기위해 프로그래머스에 들어갔다.

AI가 내가 부족한 문제 유형을 추천해주었는데, 바로 이 하노이의 탑 문제였다.

 

내가 매번 힘들어하던 문제이고, AI의 통찰력에 감탄한다,, 다시는 잊어버리지 않도록 블로그로 정리하려고한다.

 

 

 

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

프로그래머스

 

 

 

문제 해결 포인트

- 전형적인 재귀호출 문제

 

- 하노이 탑 원리 이해하기

 * 3개의 기둥에서 가장 왼쪽에 위치한 N개의 기둥을 가장 오른쪽으로 모두 옮기는 문제

 * 작은 탑이 큰 탑 아래 위치할 수 없다.

 * 한 번에 하나의 탑만 옮길 수 있다.

 

하노이탑 문제 목표

 

- N개의 탑, 옮기는 순서를 생각해보자

 

1. 맨 아래 탑을 시작위치(1)에서 목표위치(3)로 옮기고싶다

2. N-1개의 탑을 시작위치(1)에서 나머지 기둥(2)으로 옮긴다.

3. 맨 아래 탑을 이제 목표위치(3)로 옮긴다.

4. N-1개의 탑을 나머지 기둥(2)에서 목표위치로 옮긴다(3)

 

여기서 주목할 점은 N-1개의 탑을 동시에 옮길 수 있는 방법은 존재하지 않는다.

그러나, 다시 자세히 생각해보면 N-1개의 탑은 N개의 탑에서 탑이 하나 빠졌을 뿐 위 옮기는 순서는 동일하게 동작한다.

 

반복 -> 재귀함수
탑의 개수, 시작위치, 목표위치, 나머지 기둥위치 -> 매개변수

 

 

작성 코드

import java.util.*;

class Solution {
	List<int[]> list = new ArrayList<>();
	public int[][] solution(int n) {
    	hanoi(n, 1, 3, 2);
        return list.toArray(new int[1][list.size()]);
    }

	public void hanoi(int n, int from, int to, int mid){
    	if(n == 0) return;
        // 1. 시작위치에서 n-1개 기둥을 나머지 기둥으로 이동
        hanoi(n-1, from, mid, to);
        // 2. 맨 밑 기둥을 목표위치로 이동
        list.add(new int[]{from, to});
        // 3. 나머지 기둥으로 옮겨둔 n-1개 기둥을 다시 목표위치로 이동
        hanoi(n-1, mid, to, from);
    }
}

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚

 

 

[참고 사이트]

List -> Array : https://hianna.tistory.com/551