대표적인 탐색 방법중 유명한 DBS, BFS 알고리즘부터 알아보자. 이전에 여러번 공부했었는데 역시 제대로 정리하고 넘어가는게 나을거 같아서 둘의 개념, 작동방식, 코드 및 결과까지 정리해보겠다.

DFS

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

🔷 개념
가능한 한 경로로 계속 깊이 들어가다가,
더 이상 진행할 수 없으면 되돌아(backtrack) 하며 탐색하는 방식.

🔷 작동 원리
시작 노드에서 한 방향으로 계속 들어감 → 막히면 이전으로 되돌아가 다른 길 탐색

재귀 또는 스택을 이용해서 구현

🔷 구조 (재귀 기반 예시)

void dfs(int node) {
    visited[node] = true;
    for (int next : graph[node]) {
        if (!visited[next]) {
            dfs(next);
        }
    }
}

🔷 사용 예시
모든 경로 탐색

백트래킹 (퍼즐, 조합, 미로 등)

사이클 찾기, 강한 연결 요소(SCC)

BFS

✅ BFS (Breadth-First Search)
너비 우선 탐색

🔷 개념
현재 노드에서 인접한 모든 노드를 먼저 방문하고, 그다음에 그 노드들의 이웃을 방문하는 방식

🔷 작동 원리
탐색 중인 노드의 이웃들을 큐(Queue)에 넣고,
순서대로 꺼내면서 탐색을 진행

🔷 구조 (Queue 기반 예시)

void bfs(int start) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int node = queue.poll();
        for (int next : graph[node]) {
            if (!visited[next]) {
                visited[next] = true;
                queue.offer(next);
            }
        }
    }
}

🔷 사용 예시
최단 거리 탐색 (미로, 게임 맵)

레벨 순 탐색 (트리 깊이, 연결 노드 확인)

경로 찾기 (가장 짧은 경로)

DFS vs BFS 비교

어떤 걸 써야 할까?

문제는 프로그래머스의 lv2, 게임 맵 최단거리 문제를 예시로 풀었다.

해당 문제는 게임 케릭터가 목적지(특정 좌표)까지 가장 가까운 거리를 찾는 문제이다. 공부한 대로라면 BFS를 쓰는 것이 맞으나 DFS로도 풀 수 있기에 시간복잡도와 메모리 사용량을 비교해보려 둘 다 풀어봤다.

• 실제로 두 풀이다 TEST CASE의 정확성 테스트는 통과했다. 하지만 DFS는 모든 경우를 다 탐색하는 방식으로 효율성 테스트에서 떨어졌다.(어떤 깊이가 가장 짧은지 전체를 탐색한 후에 결정가능)
• 반면, BFS는 가장 짧은 최단거리를 찾는 순간 종료시키기 때문이다.

1. DFS 풀이 및 결과

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    int answer=Integer.MAX_VALUE;
    
    public int solution(int[][] maps) {
        boolean[][] visited = new boolean[maps.length][maps[0].length];
        
        dfs(maps, visited, 0, 0, 1);
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
    
    private void dfs(int[][] maps, boolean[][] visited, int row, int col, int count){
        
        int maxRow = maps.length;
        int maxCol = maps[0].length;    
            
        if(row>maxRow-1||
           col>maxCol-1||
           row<0||col<0||
           maps[row][col]==0||
           visited[row][col]==true) return;
         
        if(row==maxRow-1&&col==maxCol-1){
            if(count<answer) answer=count;
            count=0;
        }
        
        visited[row][col] = true;
        
        dfs(maps, visited, row+1, col, count+1);
        dfs(maps, visited, row, col+1, count+1);
        dfs(maps, visited, row-1, col, count+1);
        dfs(maps, visited, row, col-1, count+1);   
        
        visited[row][col] = false;
        
    }
    
}

2. BFS 풀이 및 결과

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(int[][] maps) {
        boolean[][] visited = new boolean[maps.length][maps[0].length];
        Queue<int[]> queue = new LinkedList<>();
        
        return bfs(queue, maps, visited);
    }
    
    private int bfs(Queue<int[]> queue, int[][] maps, boolean[][] visited){
        int n = maps.length;
        int m = maps[0].length;
        int[] dx = {-1,1,0,0};
        int[] dy = {0,0,-1,1};
        
        queue.offer(new int[]{0, 0, 1});
        visited[0][0] = true;
        
        while(!queue.isEmpty()){
            int[] curr = queue.poll();
            int x = curr[0];
            int y = curr[1];
            int dist = curr[2];
            
            if(x==n-1 && y==m-1) return dist;
            
            for(int i=0; i<dx.length; i++){
                int nx = x+dx[i];
                int ny = y+dy[i];
                
                if(nx>=0&&
                   ny>=0&&
                   nx<n&&
                   ny<m&&
                   maps[nx][ny]==1&&
                   !visited[nx][ny]){
                    
                    visited[nx][ny]=true;
                    queue.offer(new int[] {nx,ny,dist+1});
                    
                }
            }
        }
        
        return -1;
    }
}