티스토리 뷰
하노이 탑 공식
알고 계시나요?
생각정리스킬이란 책을 읽고 있습니다.
작가가 생각정리 관련 내용을 설명을 하다 하노이탑(Tower of Hanoi)을 설명하였습니다.
하노이탑이 궁금해졌습니다
그래서 구글플레이 스토어에서 바로 다운을 받았습니다.
규칙은 간단합니다.
아래 그림과 같이 맨 왼쪽에 원반이 크기 순서대로 쌓아져 있습니다.
이 원반을 그대로 맨 왼쪽으로 옮기면 됩니다.
1) 원반을 한번씩 이동할 수 있습니다.
2) 작은 원반 위에 큰 원반을 올릴 수 없습니다.
이 규칙을 따라서 최소 횟수로 원반을 옮기면 됩니다.
원반 수는 게임하는 것에 따라 줄일 수도 있고 늘릴 수도 있습니다.
규칙은 동일합니다.
처음에 이것저것 생각없이 게임을 진행하였습니다.
큰 방향성과 원리를 이해 못하니 잘 못하겠더라고요.
그래서 원리를 좀 생각해보았습니다.
원리를 생각하니 그리 어렵지 않았습니다.
제목을 공식이라고 썼는데 이 방식이 맞는지는 읽으신 분들이 생각해보세요.
저는 이 방법으로 최소 횟수로 게임을 완료하였습니다.
제일 처음 생각한 것은 가장 큰 원반을 맨 오른쪽에 갖다두는 것입니다.
그렇게 하기 위해서는 제일 큰 원반을 제외한 모든 원반을 두번째로 옮겨야 합니다.
그래야 가장 큰 원반(파란색)을 맨 오른쪽으로 옮길 수 있습니다.
위의 그림같은 상황을 만들기 위해서는 두번째로 큰 원반(빨간색)을 두번째 장소로 옮겨야 합니다.
그러기 위해서는 빨간색보다 작은 원반들이 모두 세번째 장소로 가있어야 합니다.
위와 같은 상황을 만들기 위해서는 세번째로 큰 원반(초록색)을 세번째 장소에 두어야 합니다.
그러기 위해서 초록색보다 작은 원반들이 두번째 장소에 가있어야 합니다.
위의 그림과 같은 상황을 만들기 위해서 두번째로 작은 원반 (검은색)이 두번째 장소에 두어야 합니다.
그러기 위해서 가장 작은 회색 원반은 세번째에 가있어야 합니다.
이렇게 목표로 한 그림을 역으로 생각해서 맨 처음 필요한 움직임을 생각해냈습니다.
지금까지 보여준 그림대로 하시면 아래 그림같은 상황을 만드실 수 잇겟죠?
이 뒤부터는 간단합니다.
파란색을 맨 오른쪽으로 옮깁니다.
그 후 빨간색만 두번째에 두고 나머지 원반을 맨 처음으로 옮기려고 생각하면 됩니다.
초록색을 맨 오른쪽으로 옮기려면 그것보다 작은 원반들은 세번째에 있어야 겠죠?
이런 원리로 진행하시면 됩니다.
특정 크기의 원반이 원하는 위치로 가기 위해서는
그것보다 작은 원반들이 다른 위치에 쌓여 있어야 합니다.
하노이 탑은 이 원리만 깨우치시면 원반 갯수가 몇개든 상관없습니다.
사실 이렇게 써놓고 보니 읽으시는 분들이 이해가 될지는 모르겠습니다.
설명자체가 어렵다면 제가 이 원리를 깨우친 방식을 다시 한번 설명드리겠습니다.
최종 목표로 생각하는 형태 맨 오른쪽에 모든 원반이 쌓여 있는 형태를 말합니다.
이렇게 되기 위해서는 제일 큰 원반이 세번째로 가야합니다.
그러기 위해서는 제일 큰 원반을 제외한 나머지 원반들이 두번째에 쌓여 있어야 합니다.
이제 제일 큰 원반을 제외한 나머지 원반들이 두번째 쌓여 있는 형태
이것을 목표라고 한다면 두번째 큰 원반을 제외한 나머지 원반들이 세번째에 쌓여 있어햐 합니다.
이런 식으로 최종 목표한 형태를 그리고 그것을 이루기 위해서 어떤 형태가 되어야 하는지
역으로 생각해내면 원리를 이해하실 수 있습니다.
이걸 공식이라고 할 수 있을지는 모르겠지만
제 나름대로 깨우친 공식입니다.
참고하세요.