1. 문제 소개


하노이 탑은 프랑스의 수학자 에두아르 뤼카가 1883년 소개한 유명한 문제로, 아래 그림을 보시면 익숙할 것이라고 생각이 듭니다. 옮기는 과정에서 작은 원반 위에 큰 원반이 놓일 수 없으며, tower 1에 있던 모든 원반이 tower 3으로 이동을 시키는 문제입니다.

2. 아이디어


어떻게 정의해야할지 잘 떠오르지 않아서 실제로 원반을 하나씩 옮겨보았습니다.

문제를 작게 만드어 해결하고 이후에 확대하는 방법이 알고리즘 문제를 푸는데 도움이 될 수 있습니다.

일단 3개의 원반을 A에서 C로 이동을 한다고 가정합니다.

친절하게 설명이 되어있는 블로그를 참조했습니다.

세개을 원반을 이동할 때 얻을 수 있는 아이디어 세 가지가 있습니다.

  1. 원반이 한 개 일때는 그냥 목표지점으로 이동을 하고 끝난다.

  2. 가장 큰 마지막 원반이 목표 지점에 도달하게 되면 그 원반을 더 이상 이동을 하지 않는다.

  3. 시작과 목표 원반이 아닌 보조원반에 가장큰 원반을 제외하고 모든 원반이 이동이 되는 과정이 있다.

3. Pseudo Code


def hanoi(원반개수, 시작, 끝, 보조)
		if 원반이 하나일 때:#시작에서 끝으로 한 번 이동시킨다.
	    print(시작, 끝)
			return
		else:
	    #원반개수-1만큼 보조 원기둥으로 이동시켜야한다
      hanoi(원반개수-1, 시작, 보조, 목표)
      #이동시킨다.
      print(시작, 보조)

      #보조 원기둥에 있는 원반을 목표 원기둥으로 이동시켜야 하기 때문에 보조기둥을 시작기둥으로 변경한다.
      hanoi(원반개수-1, 보조, 목표, 시작)

5. 간단 설명 정리