SWEA 미로 1 문제를 통해 알아보는 DFS / BFS

 

SW Expert Academy

 

---

DFS

---

	/**
     * DFS는 4방 탐색 후 갈 수 있는 곳으로 재귀를 불러 시스템 스택을 쌓는다.
     * */
    public static void DFS(int startR, int startC) {
        //상 하 좌 우 
        int[][] drc = {{-1,0},{1,0},{0,-1},{0,1}};
         
        for(int direc=0;direc<4;direc++) {
            int row = startR+drc[direc][0];
            int col = startC+drc[direc][1];
             
            //경계체크
            if(row<0 || row>=16 || col<0 || col>=16) continue;
             
            //case 1. 벽을 만나면 다른 경로 찾기
            if(map[row][col]==1) continue;//벽을 만나도 전체 미로 찾기를 종료하면 안됨 다른 경로를 찾아야 한다.
             
            //case 2. 탈출구를 만나면 return 
            if(map[row][col]==3) {
                flag=true;//탈출가능 
                return;
            }
             
            //case 3. 통로를 만나면 시스템 스택 쌓기
            //방문을 체크해주는 이유 인접한 다음 위치에서 4방탐색하며 방문했던 현재 위치를 또 방문할 수 있기 떄문이다.
            if(!visited[row][col] && map[row][col]==0) {
                visited[row][col]=true;
                DFS(row,col);//이 row, col에서 새로운 시작 
            }
        }
    }

 

 

 

---

BFS

---

	/**
     * 출발지점을 queue에 집어넣고, 방문처리한다.(출발지점을 구지 넣는 이유는 q가 첫 시작부터 비면 안되기 때문이다.)
     * 4방 탐색하면서 갈 수 있는 경로 모두를 queue에 넣고 방문처리한다.
     * 이 작업을 queue가 빌 때까지 계속한다. 
     * queue가 빈다는 것은 더이상 갈 수 있는 경로가 없다는 것을 의미한다.
     * */
    static public void BFS(int startR, int startC) {
        //상 하 좌 우 
        int[][] drc= {{-1,0},{1,0},{0,-1},{0,1}};
         
        Queue<node> queue = new LinkedList<>();
        node startNode = new node(startR, startC);
        queue.offer(startNode);
         
        while(!queue.isEmpty()) {
            //현재 시작할 노드를 뽑기
            node curr = queue.poll();
             
            //4방탐색 
            for(int i=0;i<4;i++) {
                int row = curr.r+drc[i][0];
                int col = curr.c+drc[i][1];
                 
                //경계체크
                if(row<0 || row>=100 || col<0 || col>=100) continue;
                 
                //벽 만났으면 
                if(map[row][col]==1) continue;
                 
                //탈출구를 만나면 flag를 true로 바꿔라 
                if(map[row][col]==3) {
                    flag=true;
                    return;
                }
                 
                //갈 수 있는 길을 만나면 queue에 추가 
                if(!visited[row][col] && map[row][col]==0) {
                    node newNode = new node(row,col);
                    queue.offer(newNode);
                     
                    visited[row][col]=true;
                }
            }//4방 탐색 끝 
        }
         
    }