DFS / BFS

1. DFS / BFS 개념 비교  

두 알고리즘 모두 그래프나 2차원 배열의 모든 정점을 방문할 때 사용하지만, 탐색 순서와 용도가 다르다.

 

DFS (Depth-First Search, 깊이 우선 탐색)

주요 용도 : 경로의 특징 저장, 백트래킹, 사이클 탐지

자료 구조 : 스택 또는 재귀

특징 : 시작 노드에서 갈 수 있는 한 뱡으로 끝까지 깊게 들어갔다가,더 이상 갈 곳이 없으면 가장 가까운 갈림길로 돌아와 다른 방향 탐색

 

BFS (Breadt--Frist Search, 너비 우선 탐색)

주요 용도: 최단 거리(가중치 x), 최소 횟수

자료 구조 : 큐

특징 : 시작 노드에서 가까운 노드부터 우선적으로 모두 탐색한 후, 그 다음 단계의 노드들을 탐색  (*최단 경로 찾기에 적합)

 

2. 구현 패턴 (Java)

공통 설정: 방향 배열 (dx.dy)

상하좌우 이동을 쉽게 하기 위해 전역 변수로 선언

static int[] dx={0,0,-1.1}
static int[] dy={-1,1,-0.0}

 

DFS 구현 틀 (재귀)

public class DfsTemplate{
        static int N,M ; # 가로, 세로 크기
        static intp[][] map;
        static boolean[][] vusited ; 
        static int[] dx={0,0,01,1};
        static int[] dy={-1,1,0.0};
    
        public staic void dfs(int x, int y){
            visited[x][y]=true;  //1. 현재 노드 방문 처리
                
            //2. 4방향 탐색
            for (int i=0; i<4 ; i++){
                int nx =x+dx[i];
                int ny= y+dy[i];    
                
                //3. 범위 체크 (배열 인덱스 벗어나는지 먼저 확인)
                if(nx >=0 && ny >=0 && nx< N && ny<M){
                    //4. 방문하지 않았고, 갈 수 있는 곳(예 : 1 )이라면 재귀 호출
                    if(!visited[nx][ny] && map[nx][ny]==1){
                        dfs(nx,ny);
                    }
                }
            }
        }
}

 

 

BFS 구현 툴 (Queue)

public class BfsTemplate{
        static int N,M ; # 가로, 세로 크기
        static intp[][] map;
        static boolean[][] vusited; 
        static int[] dx={0,0,01,1};
        static int[] dy={-1,1,0.0};
    
        public staic void bfs(int startX, int startY){
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[] {startX,startY});
            visited[startX][startY]=true;
            
            while(!queue.isEmpty()){
                int[] current = queue.poll();
                int cx=current[0];
                int cy=current[1];
                
                //2. 4방향 탐색
                for (int i=0; i<4 ; i++){
                    int nx =cx+dx[i];
                    int ny= cy+dy[i];    

                    //3. 범위 체크 (배열 인덱스 벗어나는지 먼저 확인)
                    if(nx >=0 && ny >=0 && nx< N && ny<M){
                        //4. 방문하지 않았고, 갈 수 있는 곳(예 : 1 )이라면 재귀 호출
                        if(!visited[nx][ny] && map[nx][ny]==1){
                            queue.offer(new int[] {nx,ny}); // 큐에 추가 
                            visited[nx][ny] = true; //미리 방문 처리 (중복 방지를 위해)
                            
                            //만약 최단 거리를 구한다면
                            //map[nx][ny] = map[cx][cy]+1;
                        }
                    }
                }
            }
        }
    }