검색어 입력폼

[알고리즘]백트래킹을 이용한 미로찾기 알고리즘 소스

등록일 2006.07.01 파일확장자압축파일 (zip) | 가격 500원

소개글

백트래킹을 이용한 미로찾기 알고리즘 소스입니다.

자바로 구현하였고 정확한 경로와 시도하였으나 틀려서 돌아온

경로도 표현합니다.

SolveMaze.class
Maze.class
Rat.class
Location.class
Direction.class
Stack.class

클래스 6개로 이루어져 있고 SolveMaze 클래스가 실행클래스 입니다.
Maze.txt 라는 맵 파일이 필요합니다. 예제로 하나 넣어 두었습니다.
구조는
12
7
111111111111
000100*************01101
100000*************11101
100000*************11111
형식으로 맨윗줄에 행 두번째 줄에 열 그리고 맵을 입력하는데 1은 벽 0은 뚫린
길입니다.

실행시에는 java SolveMaze maze.txt 라고 하시면 됩니다

컴파일 실행환경

자바가 컴파일 되는 환경이면 문제 없습니다.

본문내용

public SolveMaze(String file){
maze = new Maze(file);
rat = new Rat(maze);
stack = new Stack();

System.out.println("***** 미로의 모양 *****\n");
maze.print();
System.out.println();
System.out.println();
System.out.println("***** 쥐가 다녀간 흔적... *****");
System.out.println("0 : 올바른 경로");
System.out.println("? : 시도했으나 막혔던 경로\n");

//쥐가 출구에 도착했는지 검사하는 반복문
while(!rat.isOut()){
Location currentLocation = rat.getLocation();
maze.markMoved(currentLocation);

boolean canmove = false;


//4가지 방향중 하나의 다음칸으로 이동가능할때
for(int d = Direction.NORTH; d<=Direction.WEST; d++){
if(rat.canMove(d)&&
(maze.whathere((currentLocation.adjacent(d)).getY(), (currentLocation.adjacent(d)).getX())!=2) &&
(maze.whathere((currentLocation.adjacent(d)).getY(), (currentLocation.adjacent(d)).getX() ) != 3) ){

stack.push(currentLocation);
rat.move(d);
canmove = true;
break;
}

압축파일내 파일목록

Direction.java
Location.java
Maze.java
maze.txt
Rat.java
SolveMaze.java
Stack.java
다운로드 맨위로