2022.06.27 「LV.2 하노이의 탑」

여느 때와 같이 프로그래머스에서 문제를 풀고 있었다. 자료구조, 알고리즘 고득점 kit를 어느 정도 풀었기 때문에, 특별한 기준을 두고 문제를 고르진 않는다. 문제들을 보다가 하노이의 탑이라는 문제가 눈에 띄었다. 워낙에 재귀 함수를 이용한 풀이로 유명하지만 실제로 한 번도 풀어본 경험이 없었다. 그래서 한번 풀어보기로 결심했다. 
근데 이게 웬걸. 생각보다 내가 재귀에 대한 개념이 부족하다는 걸 느끼면서 푸는 시간과 이해하는 시간이 거의 3일은 걸렸던 것 같다. 
프로그래머스에서 같은 레벨이라도 난이도는 천차만별인듯하다. 당장에 카카오 기출만 보더라도...(기준이 뭘까..)
어찌 됐든 겨우 이해해서 그 풀이과정을 기술해볼 생각이다.

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

코딩테스트 연습 - 하노이의 탑

문제 설명

 

하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.

1. 한 번에 하나의 원판만 옮길 수 있습니다.
2. 큰 원판이 작은 원판 위에 있어서는 안됩니다.

하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.

1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return 하는 solution를 완성해주세요.

 

제한 사항

• n은 15이하의 자연수 입니다.

풀이 과정

대략 이러한 문제다. 원판이 이동하는 결과를 2차원 배열로 반환하라는 문제다. 

 

문제를 보고 한참 생각했다. 분명 재귀 관련 문제로 유명하기 때문에, 반복되는 주기가 있을 것이라 생각했다. 그 규칙을 찾는 것이 이 문제의 핵심이다. 

문제에서 주어진 예시는 n = 2 일 때의 예시이다. 그럼 n = 3 일 때도 생각해보자. 

 

참조 : https://small-stap.tistory.com/73

[프로그래머스] 하노이의 탑 Java 풀이

그림은 다른 포스팅에서 잠시 가져왔다.

 

원판이 2개

원판이 두개일 때 첫 번째 원판은 기둥 2로 간 뒤 두 번째 원판은 기둥 3으로 간다. 그 후 기둥 2의 첫 원판을 기둥 3으로 보낸다. 1 -> 2 / 1 -> 3 / 2 -> 3 

 

원판이 3개

원판이 세개일 때 원판 1 -> 기둥 3, 원판 2 -> 기둥 2, 원판 1 -> 기둥 2, 원판 3 -> 기둥 3, 원판 1 -> 기둥 1, 원판 2 -> 기둥 3, 원판 1 -> 기둥 3의 과정이다.

1 -> 3 / 1 -> 2 / 3 -> 2 / 1 -> 3 / 2 -> 1 / 2 -> 3 / 1 -> 3 의 

 

중요한 규칙은 마지막 원판 전 모든 원판들은 경유지를 거쳐 중간 지역에 모두 머무르게 되고, 마지막 원판은 경유지로 바로 간다.

 

 이걸 n개의 원판이라고 생각한다면 n-1개의 원판들은 각자의 경유지들을 거쳐 중간 지역으로 옮기고 마지막 원판은 도착지로 옮긴 뒤, 나머지 원판들을 각자의 경유지를 거쳐 도착지로 이동시키면 된다는 뜻이다.

 

이것을 코드로 구현해야 한다. 재귀를 어떤식으로 이용할 수 있을까?

 

이 부분은 도무지 떠오르지 않아 여러 풀이들을 보고 나만의 풀이를 정립했다. 

원판들이 기둥을 옮겨가는 동작을 하는 메서드를 새로 정의했다. 

 

원판의 개수가 1일 경우 바로 1 -> 3으로 가는 배열에 값을 집어넣고 리턴한다. 

아닐 경우 3가지 단계로 나누어진다.

 

첫째, n-1 개의 원판을 경유 지역으로 이동시킬 것. 

이 경우는 재귀를 이용해 파라미터에서 경유지는 마지막 기둥으로 두고 실행한다.

 

둘째, 가장 큰 마지막 원판을 마지막 기둥으로 이동시킨다. 

이 경우는 배열에 값을 직접적으로 추가한다. 

 

셋째, 경유지에 있는 n-1개의 원판을 마지막 기둥으로 옮기기 위해 다시 재귀 호출한다.

이 경우는 재귀를 이용해 파라미터에서 경유지는 중간 지역으로 두고 실행한다.

 

DFS를 이용한 풀이

 

코드로 표현하자면

 

 

이 문제를 풀면서 재귀 호출에 대해 개념을 잘못 잡고 있었다는 생각을 했다. 재귀 호출이 일어나면 자기 자신을 바로 호출하는 것이 맞지만 그만큼 메서드 메모리가 하나 더 생성되어 파고드는 것이다. 그 경우를 생각하지 못하고 문제를 풀다 보니 당연히 이해가 시간이 오래 걸린 것이다. 재귀의 개념을 확실히 이해하고 3일 내내 쳐다보니 겨우 이해가 되었다. 생각지도 못한 문제였고, 개념을 좀 더 잘 다져가야겠단 생각이 들었다.