[알고리즘] 하노이의 탑

2 min readApr 5, 2020

하노이의 탑은 볼때마다 이해가 안되던 문제였다. 이걸 보면서 재귀를 더 어렵게 느끼곤 했다. 이번에도 역시 시원하게 풀지 못했지만 조금 이해가 된 듯 하다.
먼저 풀이를 보면 다음과 같다.
python

def hanoi(n, from_pos, to_pos, aux_pos):
  if n == 1:
    print(from_pos, "->", to_pos)
    return  hanoi(n-1, from_pos, aux_pos, to_pos)
  print(from_pos, "->", to_pos)
  hanoi(n-1, aux_pos, to_pos, from_pos)

rust

fn hanoitower(n: u32, from_pos: &'static str , to_pos: &'static str, aux_pos: &'static str) {
  if n == 1 {
    println!("{}", format!("{} -> {}", from_pos, to_pos));
    return;
  }
  hanoitower(n-1, from_pos, aux_pos, to_pos);
  println!("{}",format!("{} -> {}", from_pos, to_pos));
  hanoitower(n-1, aux_pos, to_pos, from_pos);
}

함수를 정의할 때 인자로 옮길 원반의 개수, 출발 기둥, 도착 기둥, 보조 기둥을 전달한다.
종료 조건은 옮길 원반의 개수가 1일 때 출발 기둥에서 도착기둥으로 옮기고 return 하는 것으로 한다.
하노이 탑을 작게 나누어 생각해보며 접근한다.
원반의 개수가 2개일 때
원반1: 출발 기둥 → 보조 기둥
원반2: 출발 기둥 → 도착 기둥
원반3: 보조 기둥 → 도착 기둥
원반의 개수가 3개일 때
원반1: 출발 기둥 → 도착 기둥
원반2: 출발 기둥 → 보조 기둥
원반1: 도착 기둥 → 보조 기둥
원반3: 출발 기둥 → 도착 기둥
원반1: 보조 기둥 → 출발 기둥
원반2: 보조 기둥 → 도착 기둥
원반1: 출발 기둥 → 도착 기둥
이렇게 써놓으니 더 복잡해 보이기는 하는데 직접 그려보거나 하는 식으로 해야 이해가 조금 되는 듯 하다.
여기서 재귀를 사용하는 논리는 이 작은 구조를 활용하는 것이다.
n-1 개 까지는 도착지가 ‘보조 기둥’이 되어야 한다.
그리고 가장 큰 마지막 원반이 도착 기둥으로 갔을 때, n-1 개의 원반을 다시 출발 기둥을 보조 기둥삼아 도착 기둥으로 옮긴다.
재귀 구조이기 때문에 print(from_pos, “→”, to_pos) 가 반복되는데 인자가 변경 되기 때문에 값들을 다르게 출력하며 알맞는 path 를 알려주는 것.
아직도 알쏭달쏭한듯 하기는 하지만 이해가 조금 더 된 듯 하긴 하다.
위의 글을 작성하고 다시 푸는데 다시 헷갈린다.
그래도 한번 정리를 해둔 것을 읽으니 좀 낫긴 하다.
하노이의 풀이가 헷갈렸던데에는 인자의 순서의 영향도 있는듯 하다.
위의 풀이에서는 출발기둥, 도착기둥, 보조기둥 순서로 전달되는데 나는 자꾸 출발기둥, 보조기둥, 도착기둥의 흐름으로 이해를 해서 헷갈리는 부분이 있었다.
그래서 풀이를 아래와 같이 변경했다.
python

def al_hanoi(n, start, middle, end):
    if n == 1:
        print(start, "->", end)
        return "end"    al_hanoi(n-1, start, end, middle)
    print(start, "->", end)
    al_hanoi(n-1, middle, start, end)

이렇게 하니 조금 더 이해가 쉽다.
그렇기는 하지만 재귀라는 개념이 여전히 잘 와닿지 않기는 한다.

[알고리즘] 하노이의 탑

Written by hansol yang

No responses yet