[Java] 깊이우선탐색 (DFS) 미로찾기 스택구현

깊이우선탐색(DFS) 최대한 깊이 내려간 후 더이상 깊이 갈 곳이 없을 경우 옆으로 이동한다.

미로찾기의 경우 최대한 한방향으로 쭉 직진한다. 더 이상 길이 없으면 스택을 pop하며 길을 찾아간다.

 

모든 노드를 방문하고자 할 경우 주로 사용하며

검색 속도는 너비우선탐색(BFS)보다 느리다.

따라서 최단 경로를 찾고 싶다면 BFS를 사용해야 한다.

---

1. map : 갈 수 있는 길은 0, 갈 수 없는 길은 1이다.

 

2. push한 길도 벽으로 변경하여 여러번 push할 수 없도록 한다. (방문 처리)

 

3. class Index : Stack에 담을 객체 ( x와 y의 좌표를 가지고 있다.)

 

4. 현재 인덱스를 저장하고 있는 Index 클래스를 매개변수로 받아

     findWay() 메서드에서 상하좌우를 탐색하고 push한다.

 

5. push한 Index를 pop해 위치를 이동한다. <- while 반복 : 종료 위치에 도착할 때 까지.

 

import java.util.Stack;

public class DfsStack {
	public static void main(String[] args) {
		//깊이 우선 탐색 실행
		dfs(0, 0);
	}
	
	// 지도
	public static int[][] map = 
			{{0,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
			{0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
			{0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0},
			{0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,0,1,0,0,0,0},
			{0,1,0,1,0,1,1,1,1,1,1,0,1,0,0,1,0,1,0,1,0,1,1,1},
			{0,1,0,1,0,1,0,0,0,0,1,0,1,1,0,1,0,1,0,1,0,0,0,0},
			{0,1,0,1,0,1,1,1,1,0,1,0,0,0,0,1,0,1,0,1,1,1,1,0},
			{0,0,0,1,0,0,0,0,0,0,1,1,1,1,0,1,0,1,0,0,0,0,0,0},
			{0,1,1,1,1,0,1,0,1,0,1,1,1,1,0,1,0,1,1,1,0,1,0,1},
			{0,0,0,0,1,1,1,0,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0},
			{1,0,1,0,1,0,0,0,1,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1},
			{0,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0},
			{0,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0},
			{0,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0},
			{1,0,1,0,0,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0},
			{1,0,1,1,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0},
			{1,0,0,0,0,0,1,0,1,0,1,1,1,0,1,0,1,0,0,0,1,0,0,0},
			{1,0,1,1,1,1,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,1,1,1},
			{1,0,0,0,0,0,0,0,1,0,1,1,0,1,1,1,1,0,0,0,0,1,0,1},
			{1,1,1,1,1,1,1,0,1,0,1,0,0,0,0,0,1,1,1,1,1,1,0,1},
			{0,0,0,0,0,0,0,0,1,0,1,1,1,1,0,0,0,1,0,0,0,0,0,1},
			{0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,1,0,1,0,1,1,1,1,1},
			{0,0,0,0,1,0,0,0,1,0,1,1,1,1,0,1,0,0,0,0,0,0,0,0},
			{1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0}};
	
	//배열의 크기
	public static int size = map.length;

	// 인덱스를 저장하는 스택
	public static Stack<Index> ms = new Stack<>();

	// 깊이우선탐색
	public static void dfs(int x, int y) { // 시작 행, 열
		Index curr = new Index(x, y);
		map[x][y] = 1; // 첫 위치 visist설정

		while (true) {
			if (curr.getX() == size - 1 && curr.getY() == size - 1) { // 골인지점 설정
				System.out.println("미로탈출 완료!");
				break;
			} else {
				findWay(curr); // 현재 위치를 기준으로 길 탐색
				Index temp = ms.pop();
				System.out.println("" + temp.getX() + " " + temp.getY() + "로 이동");
				curr.setX(temp.getX()); // 현재 위치를 pop으로 변경
				curr.setY(temp.getY());
			}
		}
	}

	// 현재 위치의 상하좌우 탐색 메서드
	public static void findWay(Index curr) {
		int x = curr.getX();
		int y = curr.getY();

		// 위 탐색
		if (x > 0) {
			if (map[x - 1][y] != 1) { // 벽이 아니면 추가
				ms.push(new Index(x - 1, y));
				map[x - 1][y] = 1; // 추가하고 벽으로 만들어버림
			}
		}

		// 왼쪽 탐색
		if (y > 0) {
			if (map[x][y - 1] != 1) {
				ms.push(new Index(x, y - 1));
				map[x][y - 1] = 1;
			}
		}

		// 오른쪽 탐색
		if (y < size - 1) {
			if (map[x][y + 1] != 1) {
				ms.push(new Index(x, y + 1));
				map[x][y + 1] = 1;
			}
		}

		// 아래 탐색
		if (x < size - 1) {
			if (map[x + 1][y] != 1) {
				ms.push(new Index(x + 1, y));
				map[x + 1][y] = 1;
			}
		}
	}
}

 

class Index

class Index {
	private int x;
	private int y;
	
	public Index() {
	}
	
	public Index(int x, int y) {
		this.x = x;
		this.y = y;
	}
	
	public int getX() {
		return x;
	}
	public void setX(int x) {
		this.x = x;
	}
	public int getY() {
		return y;
	}
	public void setY(int y) {
		this.y = y;
	}
}

 

 

。。。

 

---