[Java 실습] DFS(깊이 우선 탐색) 미로 탐색(스택)

map : 길 = 0, 갈수 없는 길(벽) = 1

 

visited 배열을 통해 들렸던 길은 다시 들리지 않는다. (boolean으로 판단)

 

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

Way() 메서드를 통해 상하좌우를 검색하고 그 값을 push한다.

 

push한 인덱스를 pop하고, 위치를 변경한다.

언제까지? 탈출 (4,4) 할때까지.

---

import java.util.Stack;

public class DfsStack {
	 // 인덱스를 저장해주는 스택
	 static Stack<Index> sStack = new Stack<>();
	 // 들린 곳을 체크해줌
	 static boolean [][] visited = new boolean[5][5];
	 // 길=0, 벽=1
	 static int[][] map = {
			 {0,0,0,0,0},
			 {0,1,1,1,0},
			 {0,0,0,1,0},
			 {0,1,0,1,0},
			 {0,1,0,0,0}};

	 public static void main(String[] args) {
		 dfs(0,0);
	  }
	 // 시작 행, 열
	 public static void dfs(int x, int y) {
		 Index hi = new Index(x,y);
		 // 방문 처리
		 visited[x][y] = true;
		 
		 while(true) {
			 // x=4, y=4
			 if(hi.getX() == 4 && hi.getY() == 4) {
				 System.out.println("탈출했습니다!");
				 break;
			 } else {
				 // 검색 과정
				 way(hi);
				 // 현재 위치를 pop
				 Index temp = sStack.pop();
				 hi.setX(temp.getX());
				 hi.setY(temp.getY());
				 // 현재 위치를 변경
				 System.out.println(""+hi.getX() +" "+ hi.getY());
				 // 방문했다고 변경
				 visited[hi.getX()][hi.getY()] = true;
			 }
		  }
	  } 
	  public static void way(Index hi) {

		 // 위로 이동
		  if(hi.getX()>0) { 
			  if(map[hi.getX()-1][hi.getY()] != 1 && !(visited[hi.getX()-1][hi.getY()])) {
				  sStack.push(new Index(hi.getX()-1, hi.getY()));
			  }
		 }
		 // 왼쪽으로 이동
		 if(hi.getY()>0) {
			 if(map[hi.getX()][hi.getY()-1] != 1 && !(visited[hi.getX()][hi.getY()-1])) {
				 sStack.push(new Index(hi.getX(), hi.getY()-1));
			 }
		 }
		 // 오른쪽으로 이동
		 if(hi.getY()<4) {
			 if(map[hi.getX()][hi.getY()+1] != 1 && !(visited[hi.getX()][hi.getY()+1])) {
				 sStack.push(new Index(hi.getX() , hi.getY()+1));
			 }
		 }
		 // 아래로 이동
		 if(hi.getX()<4) { 
			 if(map[hi.getX()+1][hi.getY()] != 1 && !(visited[hi.getX()+1][hi.getY()])) {
				 sStack.push(new Index(hi.getX()+1, hi.getY()));
			 }
		 }
	 }
}

 

 

---

느낀점

 

최근 들어 내가 직접 코드를 짜지 못하고 코드 리딩만 하고 넘긴 실습들이 많았었는데, 이번에는 친구들과

설계를 같이 하고, 나만의 코드를 짜보고자 했던 것이 약간의 도움을 통해 다 짜냈다는거에 대해

뿌듯함을 느꼈다.

 

조금 더 열심히 공부해서, 친구들의 도움을 받지 않고 나만의 코드를 짜고, 친구들에게 도움을 줄 수 있는 사람이 돼야지.