반응형
하노이탑 3층 풀이에 이어 4층, 5층 풀이 입니다. 3층 풀이를 보시지 않으신 분들은 4층 풀이를 보기 전에 먼저 3층 풀이에 있는 '처음에 어떤 기둥으로 옮길 것인지'를 결정하는 방법과 3층 풀이를 충분히 보시기 바랍니다.
여기서는 3층 풀이에 해당하는 부분은 어느정도 생략되어 있습니다.
아래 link는 컴퓨터 상에서 해 볼 수 있는 하노이탑 게임입니다. 아래 설명을 보시면서 직접 해 보시면 더 이해가 쉬우실 것입니다.
하노이탑 4층 풀이
아래의 4개 층으로 된 탑을 1번 기둥에서 3번 기둥으로 옮기는 것입니다.
1번째 옮겨갈 위치는 4개 층이므로 3,2,3,2로 2번 기둥입니다.
그리고 3층 옮기기와 동일하게 하여 아래와 같이 3층을 2번 기둥으로 옮깁니다.
드디어 제일 큰 층을 목표기둥인 3번으로 옮길 수 있습니다.
이제 2번 기둥에 있는 3층탑을 3번 기둥으로 옮겨야 됩니다. 다음 차례에 제일 작은 층을 1, 3 번 기둥 중 어디로 옮겨야 할까요?
3개 층으로 된 탑을 3번으로 옮기는 것과 동일하기 때문에 3,1,3로써 3번 기둥으로 옮기면 됩니다.
역시 중간과정은 3층 옮기는 것과 동일합니다.
전체 15번으로 옮기기가 완료되었습니다.
하노이탑 5층 풀이
4층까지 했다면 그 이상의 층에서도 방법은 동일합니다. 중간에 어느쪽으로 옮겨갈 것인지만 잘 결정하시면 어려움이 없습니다.
처음 옮길 위치는 3,2,3,2,3으로 3번 기둥입니다.
3층 옮기기의 과정으로 아래와 같이 되었습니다.
4층 옮기기와 마찬가지로 4번째 층을 2번 기둥으로 옮깁니다.
이제 3번 기둥에 있는 3층탑을 2번으로 옮기는 과정입니다. 처음 옮길 위치는 2,1,2로 2번 입니다.
이렇게 해서 3층 옮기기가 완료되면 결과적으로 2번 기둥으로 4층옮기기가 완료되었습니다.
이제 제일 큰 층을 목표기둥인 3으로 옮깁니다.
2번 기둥의 4개층을 3번기둥으로 옮기는 것과 동일합니다.
처음 옮겨가야 할 곳은 3,1,3,1로 1번 기둥입니다.
3층 옮기기까지 완료되었습니다.
이제 2번에 있는 층을 기둥으로 3으로 옮기고 나서 보니 1번 기둥의 3층탑을 3번 기둥으로 옮기는 과정만 남았네요.
역시 다음에 옮길 위치는 3,2,3으로 3번 기둥입니다.
모두 31번의 과정을 통해 5층탑의 이동이 완료되었습니다.
이렇게 3, 4, 5층의 하노이탑을 옮기는 과정을 살펴보았습니다.
여기까지 하셨다면 지금까지와 동일한 방법으로 6, 7, 8 혹은 그 이상의 층도 문제없이 하실 수 있다는 걸 아실 것입니다.
앞에서도 말씀드렸지만 중간에 어느층으로 이동할지만 잘 결정하시면 순서가 뒤섞이는 일 없이 끝까지 해 내실 수 있으실 것입니다.
반응형
