DFS java

🍕깊이 우선 탐색 : 

 

미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.

 

 

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog

 

 

깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다. 

 

최단경로를 찾자면 BFS를 이용해야 한다. 

    DFS는 최단 경로가 된다는 보장도 없을 뿐더러 경로가 다수라면, 해에 다다르면 탐색이 종료되므로 최적 해가 아닐 수도 있다. 

 

 

   BFS와 마찬가지로 미로탐색에 해당함. 

 

타겟은 B

B 까지 가려 한다.

 

 

돌린 로직의 중간 경로를 확인 하면 다음과 같다. 

 

방문한 경로를 표시했다.

 

 

구현 : DFS + 재귀 : 

 

static int dx2[] = {1, -1, 0, 0};
static int dy2[] = {0, 0, 1, -1};
static String arr2[][];
   
   static void dfsRecursion(String[][] arr, boolean[][] visited, int x, int y) {
    
    // 종료조건이 없다면 무한루프에 빠질 수도 있다.
    // 적합한 종료조건을 명시해줌이 좋다. 가령 미로에 대한 해답이 없을 수도 있으니까.
    
            // 찾아가는 경로 확인용.
     /* for (int i = 0 ; i < lineNums2; i ++ ) {
            for (int j = 0 ; j < charNums2; j ++ ) {
                if (visited[j][i]) {
                    arr2[j][i] = "*";
                }
                System.out.print(arr2[j][i]);
            }
            System.out.println("");
        }
     */
     
     	// 목적지는 B가 되기 때문에.
         if (arr[x][y].equals("B")) {
            System.out.println("B found...");
           
            cnt2++;
            return;
        }
     
     // 방문한 경로에 대한 표시를 한다. 
     visited[x][y] = true;
     
         for (int i=0;i<4;i++) {

            int nx = x + dx2[i];
            int ny = y + dy2[i];

            if (nx >=0 && ny >=0 && nx < charNums2 && ny < lineNums2) {
                if ((!visited[nx][ny] && arr[nx][ny].equals(" ") ) || arr[nx][ny].equals("B")) {
                    dfsRecursion(arr,visited,nx,ny);
                    visited[nx][ny] = false;  
                }
            }
        }