[Go] 하노이의 탑

3h

프로그래머스

Lv.2 치고 해결하는데 시간이 꽤나 걸린 문제

재귀 연습을 하기에 좋은 문제

 

문제를 읽고 1~2시간 정도는 멍때리며 코드는 작성하지 못했다. 

N = 3, N = 4, N = 5 일 때 실행 과정을 직접 종이에 그려보며 일련의 규칙을 찾아냈다.

 

3개 축에서 시작 축에 놓여진 N개의 원판을 목적 축으로 옮기는 방법은 아래와 같다.

src축에 놓인 N개의 원판

 

Step 1. 맨 아래 가장 큰 원판 하나를 제외한 N-1개의 원판을 남는 축으로 옮긴다.

Step 1

 

 

 

Step 2. 맨 아래 가장 큰 원판을 목적 축으로 옮긴다.

Step 2

 

 

 

Step 3. N-1개의 원판들도 목적 축으로 옮긴다.

Step 3

 

 

위 과정을 의사코드로 작성하기 위해 총 4가지의 파라미터가 필요

- 원판 개수 ( n )

- 시작 축 ( src ) 

- 목적 축 ( dst )

- 남는 축 ( via )

hanoi(n, src, via, dst) 
   /* 종료 조건 생략 */
   hanoi(n-1, src, via, dst)

   move(src, dst)

   hanoi(n-1, via, src, dst)

 

종료 조건은 단순히 원판이 한 개인 경우를 생각하면 된다. 

원판이 한개라면 시작 축에서 목적 축으로 바로 옮기면 끝

hanoi(n, src, via, dst) 
   if n == 1 
      move(src,dst)
      exit
   hanoi(n-1, src, via, dst)
   move(src, dst)
   hanoi(n-1, via, src, dst)

 

Golang으로 작성한 전체 코드

var moves [][]int

func solution(n int) [][]int {
    hanoi(n,1,2,3)
    return moves
}
func move(src,dst int){
    moves = append(moves, []int{src,dst})
}
func hanoi(n, src, via, dst int){
    // 원판이 한개라면 옮기고 끝
    if n == 1 {
        move(src,dst)
        return
    }
    // hanoi는 크게 3가지 과정으로 나뉜다.
    // 1. 맨 아래 가장 큰 원반을 옮기기 전 나머지 n-1개를 경유축으로 옮기는 과정
    hanoi(n-1, src, dst, via)
    // 2. 맨 아래 가장 큰 원반을 목적축으로 옮기는 과정
    move(src,dst)
    // 3. 경유축에 옮겨진 n-1개의 원반을 목적축으로 옮기는 과정
    hanoi(n-1, via, src, dst)
}