[CS] DFS와 BFS의 원리와 구현 방식 (JAVA)

DFS

DFS(Depth-First Search)는 깊이 우선 탐색이라고 부른다.

출처 : 위키백과

• 한 경로로 최대한 깊숙하게 들어가서 탐색한 후 다시 돌아가 다른 경로를 탐색하는 방식
• 일반적으로 재귀함수를 이용하여 구현하며 Stack을 이용하여 구현하기도 함
• 구조상 Stack Overflow에 유의해야 함
• DFS 활용 : 백트랙킹, 단절선 찾기, 위상정렬, 사이클 찾기 등 

 

DFS 구현

1. 체크인
2. 목적지인가?
3. 연결된 곳을 순회
4. 갈 수 있는가?
5. 간다
6. 체크아웃

static int[][] graph;
static boolean[] visited;

static void dfs(int index) {
    // 1. 체크인
    visited[index] = true;
    
    // 2. 목적지인가?
    if (종료조건) {
    	작업 수행
    }
    else {
        // 3. 연결된 곳을 순회
        for (int node : graph[index]) {
            // 4. 갈 수 있는가?
            if (!visited[node]) {
                // 5. 간다
                dfs(node);
            }
        }
    }
    
    // 6. 체크아웃
    visited[index] = false;
}

 

BFS

BFS(Breadh-First Search)는 너비 우선 탐색이라고 부른다.

출처 : 위키백과

• 시작 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방식
• 일반적으로 Queue 자료구조를 이용하여 구현
• BFS 활용 : 최단경로 찾기, 위상정렬 등

 

BFS 구현

1. 큐에서 꺼냄
2. 목적지인가?
3. 연결된 곳을 순회
4. 갈 수 있는가?
5. 체크인
6. 큐에 넣음

static int[][] graph;
static boolean[] visited;

static void bfs(int index) {
    Queue<Object> queue = new LinkedList<>();
    visited[index] = true;
    queue.offer(index);
    
    while (!queue.isEmpty()) {
        // 1. 큐에서 꺼냄
        Object obj = queue.poll();

        // 2. 목적지인가?
        if (종료조건) {
            작업 수행
            break;
        }
        
       	// 3. 연결된 곳을 순회
        for (int node : graph[index]) {
            // 4. 갈 수 있는가?
            if (!visited[node]) {
                // 5. 체크인
                visited[node] = true;
                // 6. 큐에 넣음
                queue.offer(node);
            }
        }
    }
}

 

DFS와 BFS 둘 중 무엇을 써야 할까?

동시에 움직여야 할 것이 있는가?

동시에 움직여야 할 것이 있다면 큐에 넣어 처리하면 되기 때문에 BFS를 사용한다.

그에 반해, DFS는 한번 들어간 경로는 끝까지 탐색하기 때문에 동시에 움직여야 하는 상황에 적합하지 않다.