JAVA 프로그래밍
문제
하노이 탑에서 출발기둥에 있는 여러 원반을 도착기둥으로 모두 옮기는 문제입니다 이를 해결하는 다음 프로그램을 해석하세요 단, 원반은 한 번에 하나씩만 옮길 수 있고, 작은 원반 위에 더 큰 원반을 옮길 수 없습니다.
하노이 탑의 원반 개수를 입력하세요(10개 이하) : 2
1 . .
2 . .
--- --- ---
A B C
. . .
2 1 .
--- --- ---
A B C
. . .
. 1 2
--- --- ---
A B C
. . 1
. . 2
--- --- ---
A B C
하노이 탑의 원반 개수를 입력하세요(10개 이하) : 3
1 . .
2 . .
3 . .
--- --- ---
A B C
. . .
2 . .
3 . 1
--- --- ---
A B C
. . .
. . .
3 2 1
--- --- ---
A B C
. . .
. 1 .
3 2 .
--- --- ---
A B C
. . .
. 1 .
. 2 3
--- --- ---
A B C
. . .
. . .
1 2 3
--- --- ---
A B C
. . .
. . 2
1 . 3
--- --- ---
A B C
. . 1
. . 2
. . 3
--- --- ---
A B C
하노이 탑의 원반 개수를 입력하세요(10개 이하) : 4
1 . .
2 . .
3 . .
4 . .
--- --- ---
A B C
. . .
2 . .
3 . .
4 1 .
--- --- ---
A B C
. . .
. . .
3 . .
4 1 2
--- --- ---
A B C
. . .
. . .
3 . 1
4 . 2
--- --- ---
A B C
. . .
. . .
. . 1
4 3 2
--- --- ---
A B C
. . .
. . .
1 . .
4 3 2
--- --- ---
A B C
. . .
. . .
1 2 .
4 3 .
--- --- ---
A B C
. . .
. 1 .
. 2 .
4 3 .
--- --- ---
A B C
. . .
. 1 .
. 2 .
. 3 4
--- --- ---
A B C
. . .
. . .
. 2 1
. 3 4
--- --- ---
A B C
. . .
. . .
. . 1
2 3 4
--- --- ---
A B C
. . .
. . .
1 . .
2 3 4
--- --- ---
A B C
. . .
. . .
1 . 3
2 . 4
--- --- ---
A B C
. . .
. . .
. . 3
2 1 4
--- --- ---
A B C
. . .
. . 2
. . 3
. 1 4
--- --- ---
A B C
. . 1
. . 2
. . 3
. . 4
--- --- ---
A B C
알고리즘
프로그램 시작
하노이 타워의 초기 상태를 설정
3개의 원반을 출발기둥, 임시기둥, 도착기둥을 이용해 이동
프로그램 종료
원반 여러 개를 이동하는 함수
N-1개 원반을 출발기둥에서 임시기둥으로 모두 이동
가장 큰 원반을 출발기둥에서 도착기둥으로 이동
N-1개 원반을 임시기둥에서 도착기둥으로 모두 이동
원반 한 개를 이동하는 함수
출발기둥의 가장 위에 있는 원반 하나 가져오기
도착기둥의 가장 위에 원반 놓기
원반 한 개를 이동한 결과 출력
프로그램 코드
// 파일명 : ./Chapter20/TowerOfHanoi.java
import java.util.Scanner;
public class TowerOfHanoi
{
private static int[][] tower = new int[3][10];
private static int[] diskCountPerTower = new int[3];
private static int totalDiskCount;
// 하노이 타워의 초기 상태를 설정하는 함수
F1b private static void initializeTower( int diskCount ) {
totalDiskCount = diskCount;
diskCountPerTower[0] = diskCount;
diskCountPerTower[1] = 0;
diskCountPerTower[2] = 0;
for ( int i = 0; i < diskCount; i++ ) {
tower[0][i] = diskCount - i;
}
F1e }
// 하노이 타워의 현재 상태를 출력하는 함수
private static void printTower() {
for ( int line = totalDiskCount-1; line >= 0; line-- ) {
for ( int number = 0; number < 3; number++ ) {
if ( tower[number][line] > 0 )
System.out.print( " " + tower[number][line] + " " );
else
System.out.print( " . " );
}
System.out.println();
}
System.out.println(" --- --- ---\n A B C \n");
}
// 원반 한 개를 이동하는 함수
F2b private static void moveOneDisk( int from, int to ) {
// 출발기둥의 가장 위에 있는 원반 하나 가져오기
int top = --diskCountPerTower[from];
int disk = tower[from][top];
tower[from][top] = 0;
// 도착기둥의 가장 위에 원반 놓기
top = diskCountPerTower[to]++;
tower[to][top] = disk;
// 원반 한 개를 이동한 결과 출력
printTower();
F2e }
// 원반 여러 개를 이동하는 함수
F3b private static void moveDisks( int diskCount, int from, int temp, int to ) {
if ( diskCount == 1 ) {
F31 moveOneDisk( from, to );
}
else {
// N-1개 원반을 출발기둥에서 임시기둥으로 모두 이동
F32 moveDisks( diskCount-1, from, to, temp );
// 가장 큰 원반을 출발기둥에서 도착기둥으로 이동
F33 moveOneDisk( from, to );
// N-1개 원반을 임시기둥에서 도착기둥으로 모두 이동
F34 moveDisks( diskCount-1, temp, from, to );
}
F3e }
// 프로그램 시작
1 public static void main( String[] args ) {
Scanner scan = new Scanner( System.in );
// 하노이 타워의 초기 상태를 설정
System.out.print( "하노이 탑의 원반 개수를 입력하세요(10개 이하) : " );
int diskCount = scan.nextInt();
2 initializeTower( diskCount );
printTower();
// 3개의 원반을 출발기둥, 임시기둥, 도착기둥을 이용해 이동
3 moveDisks( diskCount, 0, 1, 2 );
scan.close();
// 프로그램 종료
4 }
}
실행 순서
※ 실행순서 및 메모리상태는 A키(이전) 및 D키(다음)를 눌러도 확인할 수 있습니다