하노이 탑(Tower of Hanoi)

Javascript로 구현한 Hanoi tower

하노이 탑은 세개의 기둥과 n개의 크기가 다른 원판이 크기가 큰 순서대로 첫번째 기둥에 꽂혀있습니다. 그리고 다음의 규칙에 맞게 세번째 기둥에 옮기면 되는 퍼즐의 일종이다.

첫번째, 한번에 하나의 원판을 옮길 수 있다.

두번째, 크기가 작은 원판 위에 큰 원판이 올 수 없다.

원판이 n개일 때, 번 이동하게 됩니다.

하노이 탑 설화

인도 베나레스에 있는 한 사원에는 세상의 중심을 나타내는 큰 돔이 있고 그 안에 세 개의 다이아몬드 바늘이 동판 위에 세워져 있습니다. 바늘의 높이는 1큐빗이고 굵기는 벌의 몸통만 합니다. 바늘 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았습니다. 가장 큰 원판이 바닥에 놓여 있고, 나머지 원판들이 점점 작아지며 꼭대기까지 쌓아 있습니다. 이것은 신성한 브라흐마의 탑입니다. 브라흐마의 지시에 따라 승려들은 모든 원판을 다른 바늘로 옮기기 위해 밤낮 없이 차례로 제단에 올라 규칙에 따라 원판을 하나씩 옮깁니다. 이 일이 끝날 때, 탑은 무너지고 세상은 종말을 맞이하게 됩니다.

 by https://ko.wikipedia.org/wiki/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98_%ED%83%91

알고리즘의 구성

기본적으로 하노이탑 알고리즘은 재귀호출을 이용하여 해결하는 구조입니다.

HanoiTower.prototype.move = function(count, from, by, to)
{
    if(count==1)
        this.columns[to].addNode(this.columns[from].pop());
    else
    {
        this.move(count-1, from, to, by);
        this.columns[to].addNode(this.columns[from].pop());
        this.move(count-1, by, from, to);
    }
}

HanoiTower.prototype.move = function(count, from, by, to)

 이 함수는 count만큼의 원판을 from기둥에서부터 to기둥까지 by기둥을 이용해서 옮기라는 함수입니다.

if(count==1)
    this.columns[to].addNode(this.columns[from].pop());

 원판이 한개일때는 그냥 해당 장소로 옮기면 됩니다. column은 스택구조로 돼있고, 제일 위에 있는 것은 가장 작은 것이므로 어디로든 옮길 수 있습니다.

else
{
    this.move(count-1, from, to, by);
    this.columns[to].addNode(this.columns[from].pop());
    this.move(count-1, by, from, to);
}

 이제 중요한 것은 위의 코드입니다.

this.move(count-1, from, to, by);

일단 to로 이동을 시키려면 가장 큰 것(가장 아래에 있는 것)이 먼저 to기둥으로 들어가야하기 때문에 일단 그 위에 있는 것들을 by기둥으로 옮겨야 합니다. 그림으로 이해해주시면 좋을 것 같습니다.

this.columns[to].addNode(this.columns[from].pop());

위에 있는 원판들의 이동이 끝났으면 가장 아래에 있는 원판을 To원판으로 옮겨줍니다.

this.move(count-1, by, from, to);

그럼 이제 by로 옮겨놨던 원판들을 to로 옮겨줍니다.

이렇게 되면 아래의 그림처럼 이동이 완료되는 형태입니다.

 이미지에서는 여러개를 묶어서 이동하는 것처럼 표현했지만, 그런것이 아니라 해당 묶음을 재귀호출을 통해 1개 단위로 거슬러 올라가서 이동하는 형태입니다.