하노이탑 알고리즘

오늘 포스팅은 하노이탑 알고리즘에 대해서 설명드리려고 합니다.

재귀함수로 표현해서 코드를 구성했는데, 다음 포스팅에서는 비재귀함수로 코드를 구성해보겠습니다.

우선 기본 틀은 다음과 같습니다.

1. 첫 번째 기둥에 (1,2,3) 원반이 있고 두 번째 기둥은 비어있고 세 번째 기둥 또한 비어있습니다.

2. 첫 번째 기둥에 있는 원반들을 온전히 세 번째 기둥으로 옮기는 과정을 겪어야합니다.

3. 하노이탑 완성 과정의 횟수를 카운트해서 출력하겠습니다.

핵심은 원반을 그룹으로 보는 것이다. 

마치 Dynamic Programming과 같은 방법이라 하면 된다.

우선 글로 설명을 먼저하고 이해를 돕기 위해 그림을 첨부하겠다.

---

<핵심>

1. 0번째 원반을 제외한 나머지 1번~n-1번째의 원반을 하나의 그룹이라 생각한다.

2. 1번~n-1번째의 원반(그룹)을 두 번째 기둥으로 옮긴다.

3. 0번째 원반을 세 번째 기둥으로 옮긴다.

4. 두 번째 기둥에 있던 1번~n-1번째 (하나의 그룹 원반) 원반을 모두 세 번째 기둥으로 옮긴다.

---

앞서 그림처럼 맨 밑에 깔린 원반을 제외하고는 다음처럼 그룹으로 움직이게 한다.

기둥은 총 3개로 처음 시작 기둥은 1, 마지막 도착 기둥은 3이라 할 때, 중간 기둥은 2로 둘 수 있다.

중간 기둥은 6-(시작기둥)-(도착기둥) 으로도 정의할 수 있다.

따라서, 맨 아래 기둥을 제외한 나머지 기둥들(하나의 그룹)은 첫 번째 기둥에서 두 번째 (중간) 기둥으로 

이동해야하므로 코드는 아래와 같다.

---

static void move(int n,int start,int end) {  

// n은 몇 개의 원반을 하노이탑 알고리즘을 통해 옮길 것인지이며, start는 시작 기둥, end는 도착 기둥을 의미한다.

if(n>1){ // 맨 아래 원반을 제외하고 이동을 해야 하기 때문에 다음과 같은 조건이 필요.

move(n-1,start,6-start-end);  // 

}

}

---

다음에는 2번째 기둥에서 마지막 기둥으로 옮기는 것이다. 

---

static void move(int n,int start,int end) {  

// n은 몇 개의 원반을 하노이탑 알고리즘을 통해 옮길 것인지이며, start는 시작 기둥, end는 도착 기둥을 의미한다.

if(n>1){ // 맨 아래 원반을 제외하고 이동을 해야 하기 때문에 다음과 같은 조건이 필요.

move(n-1,start,6-start-end);  // 

}

if(n>1){

move(n-1,6-start-end,end);

}

}

---

전체 코드는 다음과 같다.

---

import java.util.Scanner;

public class Hanoi {

static int ret = 0;

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner scanner = new Scanner(System.in);

System.out.println("하노이의 탑");

System.out.println("원반 갯수 : ");

int n = scanner.nextInt();

move(n, 1, 3);

System.out.println("이동 횟수 :  " + ret);

}

static void move(int n, int start, int end) {

// 원반[1] ~ 원반[n-1]은 중간 기둥에 옮기고

// 원반[0]은 목표 기둥으로 옮긴다.

// 원반[1] ~ 원반[n-1]이 통째로 목표기둥으로 옮겨간다.

if (n > 1) {

// n이 1보단 커야함 --> 원반 마지막 기둥은 남겨야 하므로

move(n - 1, start, 6 - start - end); // start : 1번기둥 , end : 3번 기둥 --> 나머지 2번 기둥은 중간이 됩니다.

}

System.out.println("이동 : " + (char) (start - 1 + 'A') + " 기둥에서 " + (char) (end - 1 + 'A') + " 기둥으로 ");

ret += 1;

if (n > 1) {

move(n - 1, 6 - start - end, end);

}

}

}

---

중간에 ret+=1 이 부분은 하노이탑 알고리즘이 진행하는 횟수이며 횟수를 main에서 출력하기 위해 전역변수로 설정하였다.