알고리즘을 공부하다보면, 재귀함수가 단골손님으로 등장한다. 간단하게 말하면 자기 자신을 다시 호출하는 것이 재귀함수인데, 보통 잘 알려진 것이 하노이의 탑이다.
하지만, 처음 알고리즘을 배우는 사람들은 "아, 그런가보다~" 하고 말지, 하노이의 탑을 어떻게 구현 해야할지는 막막하다.
지금부터 간단하게 하노이의 탑을 살펴보고, 자바로 하노이의 탑을 구현해보자.
#2. 하노이의 탑?
* 하노이의 탑에 대해서 자세하게 알고 싶으면 인터넷 검색을 추천한다.
알고리즘 구현에 앞서, 간단하게 큰 특징을 정리해보면 다음과 같다.
1) 탑을 구성하는 원판은 번호(혹은 크기)가 모두 다르다.
2) 항상 번호(혹은 크기)가 큰것이 아래로 가야한다.
3) 쌓여있는 탑을 다른 기둥으로 똑같이 쌓아야 하며, 움직일 수 있는 원판은 한 번에 하나씩만 가능하다.
4) 원판을 움직일 때, 각 기둥의 가장 위에 위치한 원판만 가능하다.
5) 움직이려는 원판을 다시 내려놓을 때, 자신의 번호(혹은 크기)가 놓으려는 원판보다 작아야 한다.
#3. Java로 구현하기
코딩을 하는 사람마다 구현하는 방법은 각자 다르겠지만, 여기서 사용한 방법은 다음과 같다. 아래의 그림처럼 먼저 클래스를 2개로 나누었고, Hanoi 클래스에서 알고리즘의 구현을 했고, Driver 클래스에서 실행을 한다.
1) Hanoi 클래스
매소드 중에 moveTower 부분을 자세히 살펴보면, 재귀함수가 사용됨을 알 수 있다.
lastMovedLine 의 숫자를 1 혹은 2로 바꿔서, 하노이 탑의 최종 위치를 변경할 수 있다.
(구지 하노이의 탑을 항상 3번째 기둥으로 옮기고자 한다면, 하노이 탑이 짝수일 경우에 lastMovedLine을 2로 해주는 로직을 추가하면 된다.)
package hanoiTower;
public class Hanoi {
private int x = 3; // fixed. A number of pillar.
private int y = -1; // height
private int[][] hanoiField;
private int[] cntLine = new int[x];
private int lastFoundLine = -1;
private int lastMovedLine = 1; // choose the place to move. (1 or 2)
private int moveCNT = -1; // moved times count
public Hanoi(int num) {
this.y = num;
this.hanoiField = new int[num][x];
}
public void initHanoiTower() {
System.out.println("Start!");
System.out.println("==========" + "\n");
// make HanoiTower
for (int i = y; i > 0; i--) {
hanoiField[i - 1][0] = i;
}
moveTower(y);
System.out.println("==========");
System.out.println("Done!");
System.out.println("Total moved count : " + moveCNT);
}
public void showTower() {
for (int i = 0; i < y; i++) {
for (int j = 0; j < x; j++) {
String s = String.valueOf(hanoiField[i][j]);
if (s.length() == 1 || s.equals("0")) {
System.out.print("| " + s.replace("0", " ")
+ blank(s.length()));
} else {
System.out.print("| " + s + blank(s.length()));
}
}
System.out.print("|");
System.out.println();
}
System.out.println("----------------" + "\n");
moveCNT++;
}
public int countLine(int num) {
for (int i = 0; i < x; i++) {
int cnt = 0;
for (int j = 0; j < y; j++) {
if (hanoiField[j][i] != 0) {
cnt = cnt + 1;
}
}
cntLine[i] = cnt;
}
return cntLine[num];
}
public int[] findNumPlace(int num) {
int[] coordinate = new int[2];
coordinate[0] = -1;
coordinate[1] = -1;
for (int i = 0; i < y; i++) {
for (int j = 0; j < x; j++) {
if (hanoiField[i][j] == num) {
lastFoundLine = j;
coordinate[0] = j;
coordinate[1] = i;
}
}
}
return coordinate;
}
public void moveTower(int num) {
int to = -1;
if (num <= 2) {
showTower();
// move 1, 2
for (int i = 1; i <= 2; i++) {
hanoiField[findNumPlace(i)[1]][findNumPlace(i)[0]] = 0;
to = x - (lastFoundLine + lastMovedLine);
hanoiField[(y - 1) - countLine(to)][to] = i;
lastMovedLine = to;
showTower();
}
// move 1 again
hanoiField[findNumPlace(1)[1]][findNumPlace(1)[0]] = 0;
hanoiField[(y - 1) - countLine(to)][to] = 1;
showTower();
} else {
// reflexive
moveTower(num - 1);
// move the tower's number bigger than 2
hanoiField[findNumPlace(num)[1]][findNumPlace(num)[0]] = 0;
to = x - (lastFoundLine + lastMovedLine);
hanoiField[(y - 1) - countLine(to)][to] = num;
lastMovedLine = to;
// shift place when the tower's number is even.
if (num % 2 == 0) {
// System.out.println("!!!!!");
lastMovedLine = lastFoundLine;
}
// move 1, 2 again
moveTower(num - 1);
}
}
public String blank(int num) {
String s = String.valueOf(this.y);
int l = s.length();
String o = " ";
for (int i = l - num; i > 0; i--) {
o = o + " ";
}
return o;
}
}
2) Driver 클래스
7번 라인 Hanoi()안의 숫자를 변경하면, 하노이 탑의 크기를 변경해서 볼 수 있도록 해두었다.
package hanoiTower;
public class Driver {
public static void main(String[] args) {
// You can change the start height of HanoiTower.
Hanoi h = new Hanoi(5);
h.initHanoiTower();
}
}
#4. 결과 화면
하노이 탑을 설명할 때 사용한 이미지와 동일하게 원판을 하나하나 움직여서 탑을 우측으로 옮긴 모습을 확인할 수 있다.
만약, 15개 짜리 하노이의 탑이라면? 직접 프로그램으로 돌려보길 바란다.
(혹은 운이 좋다면, 정확하게 32,767회의 움직임 끝에 하노이 탑을 모두 옮길 수 있을 것이다.)
댓글 없음:
댓글 쓰기