반응형
하노이탑(하노이 타워)를 잘 할 수 있는 방법을 소개해 드립니다.
작년엔가 모 방송사의 스펀지라는 프로그램에서 공부잘하는 방법으로 소개된 것 중의 하나가 하노이탑입니다.
6살 아이에게 시켜 봤더니 꽤 흥미있어하며 오랫동안 집중력을 보이더군요.
직접 하다보면 그 속에 숨어있는 풀이방법의 원리를 깨우치게 되겠지만, 여기서는 부모나 이 게임을 가르쳐 주고자 하는 분들을 위해 그 풀이의 원리를 간단히 소개 드립니다.
이번에는 간단히 게임의 규칙과 처음 옮겨야 할 탑의 위치, 그리고 3층탑을 옮기는 방법을 소개해 드리겠습니다.
다음에는 4층, 5층, 그리고 그 이상의 층에 대해서도 옮기는 원리를 말씀드리겠습니다.
아래 link는 컴퓨터 상에서 해 볼 수 있는 하노이탑 게임입니다. 아래 설명을 보시면서 직접 해 보시면 더 이해가 쉬우실 것입니다.
게임의 목표
1. 한 쪽 기둥에 크기 순서대로 쌓여 있는 여러 층의 탑을 동일한 순서대로 다른 기둥으로 옮기는 것
위의 그림처럼 1번 기둥에서 아래 규칙대로 움직여서 최종적으로 3번 기둥으로 옮기는 거죠.
게임 규칙
1. 한 번에 한개의 층만을 다른 기둥으로 옮길 수 있다
2. 옮기려는 기둥에는 아무것도 없거나 옮기려는 층보다 큰 층이 있을 경우에만 옮길 수 있다
3. 옮기려는 기둥에 옮기려는 층보다 작은 층이 이미 있을 경우 그 기둥으로 옮길 수 없다.
4. 가능한 적은 회수로 전체 탑을 다른 기둥으로 옮긴다.
위 그림에서와 같이 2번 기둥에 있는 층은 자신보다 큰 층이 있는 1번 기둥으로는 옮길 수 있으나 자신보다 작은 층이 있는 3번 기둥으로는 옮길 수 없습니다.
처음 옮겨가야 할 기둥은 어디?
하나의 층이 옮겨갈 수 있는 곳은 최대 두군데 입니다. 아래 그림처럼 1번 기둥에 탑이 쌓여 있고 최종적으로 3번 기둥으로 모두 옮기고자 할 경우 제일 처음에 제일 작은 층은 2번 기둥으로 가야 할까요? 아니면 3번 기둥으로 가야할까요?
처음에 어디로 옮기느냐에 따라 마지막에 전체 탑이 어느 기둥으로 옮겨지는지 결정됩니다.
제일 처음 옮겨가야 할 기둥은 다음과 같이 간단히 결정할 수 있습니다.
- 제일 밑에 있는 층이 목표인 3번 기둥으로 간다
- 그 위의 층은 다른 기둥인 2번으로 간다
- 다시 그 위의 층은 앞의 기둥과 다른 2번 기둥으로 간다
이렇게 하면 3층인 탑은 3,2,3으로 제일 처음 3번 기둥으로 옮기면 됩니다. 마찬가지로 8층 탑의 경우는 3,2,3,2,3,2,3,2로 제일 처음 2번 기둥으로 옮겨야 합니다.
3층탑 옮기는 방법
다음은 3층탑을 옮기는 방법입니다.
첫번째 옮기는 위치는 앞에서 알아본 봐와 같이 목표인 3번 기둥입니다.
그 다음 두번째로 큰 층을 비어 있는 2번 기둥으로 옮깁니다.
제일 작은 층을 다시 두번째 층 위로 옮깁니다.
제일 큰 층을 목표인 3번 기둥으로 옮깁니다.
제일 작은 층을 비어 있는 1번 기둥으로 옮깁니다. 여기서도 2번 기둥에 있는 2층 탑을 3번으로 옮긴다고 생각하면 제일 작은 층이 어디로 가야할 지는 쉽게 결정할 수 있습니다. (앞에서의 방법에 따라 3,1로 1번 기둥으로 가야겠죠..)
드디어 모든 층이 3번 기둥으로 옮겨져서 게임을 끝내게 됩니다.
3층 탑 옮기기가 익숙해 지면 앞에서 이야기 한 처음 옮겨가야 기둥을 정하는 방법과 3층탑 옮기기를 응용하여 3층 이상의 탑도 쉽게 옮길 수 있게 됩니다.
참고로 층의 개수에 따른 최소로 옮길 수 있는 회수는 다음과 같습니다.
n층의 최소 회수 = 2의 n승 -1
3층일 경우 2의 3승 -1 이므로 2x2x2-1 = 7
4층일 경우 2의 4승 -1 이므로 2x2x2x2-1 = 15
8층일 경우 2의 8승 -1 이므로 2x2x2x2x2x2x2x2x-1 = 255
반응형
