DFS와 BFS에 대해

참고: 취업과 이직을 위한 프로그래머스 코딩 테스트 문제 풀이 전략. 김현이.

DFS

기본 개념

      1
     / \
    2   3
   / \   \
  4   5   6

• 진행 방향: 1 - 2 - 4 - 5 - 3 - 6 (전위 순회)
• 한 쪽 끝까지 탐색 후 다시 돌아와서 다음 경로 탐색
• 탐색 공간이 제한되어 있고, 탐색 공간 내 탐색 목표가 있는지 검사할 때 유용
• 탐색 공간의 깊이가 제한되어 있지 않으면 적용하기 어려움
  • 즉, 완전 탐색이 가능할 때 적용
• 최단 경로 찾기 어려움

주로 사용하는 자료구조 및 기법

스택

스택은 후입선출(LIFO)로, 탐색하다 막히면 이전 노드로 되돌아가야 하기 때문에 많이 사용된다.

재귀

재귀는 함수가 호출될 때마다 함수 호출 스택이 쌓이기 때문에 스택을 따로 사용하지 않아도 그 역할을 한다.

코드 템플릿

import java.util.*;

// (1) 방문했는지 검사하는 배열 선언
boolean[] isVisited = new boolean[N];

Stack<Integer> stack = new Stack<>();
// (2) 초기 상태 설정
stack.add(/* initialState = */ 0);

// (3) 탐색
while(!stack.isEmpty()) {
    int state = stack.pop();
    
    // (4) 중복 검사. 이미 방문한 노드라면 그 전 노드로 돌아감
    if (isVisited[state]) continue;
    isVisited[state] = true;

    // (5) 현재 상태 처리
    /* 현재 상태 state 처리. sum이라든지... */

    // (6) 전이 상태(state) 생성
    for (int next : getNextStates(state)) {
        // (7) 범위 검사
        if (!/* 범위 검사 조건 */) {
            // 문제 범위를 벗어나는 상테는 제외
            // 예: Index Out of Range
            continue;
        }
        // (8) 유효성 검사
        if (!/* 유효성 검사 조건 */) {
            // 문제의 조건을 어기는 상태는 제외
            continue;
        }

        // (9) 상태 전이
        stack.push(next);
    }
}

BFS

기본 개념

      1
     / \
    2   3
   / \   \
  4   5   6

• 진행 방향: 1 - 2 - 3 - 4 - 5 - 6
• 초기 상태와 가장 가까운 상태부터 탐색
• 목표 상태에 도달할 수 있는 가장 빠른 경로를 탐색하는 데 유용
• 탐색 공간의 깊이에 제한이 없음

주로 사용하는 자료구조

큐

BFS는 현재 노드와 가까운 노드부터 탐색하기 때문에, 먼저 방문한 노드를 먼저 처리해야 한다. 따라서 선입선출(FIFO)인 큐를 많이 사용한다.

우선순위 큐(PriorityQueue)

자바로 여행순서(?) 문제를 풀다 알게 된 자료구조다.
우선순위 큐는 정렬을 해주는 큐라고 생각하면 되는데, Comparator를 통해 내가 원하는 방식으로 우선순위를 설정할 수 있다.
poll()을 호출하면 값이 가장 작은(우선순위가 가장 높은) 값이 나온다.

코드 템플릿

import java.util.*;

boolean[] isVisited = new boolean[N];

Queue<Integer> queue = new LinkedList<>();
queue.add(/* initialState = */ 0);
isVisited[/* initialState = */ 0] = true;

while (!queue.isEmpty()) {
    int state = queue.poll();

    /* 현재 상태 state 처리 */
    
    /* 
     * getNextStates는 최단 경로 찾는 문제에서선
     * 상하좌우로 움직인 좌표가 상태가 되기도 한다.
     */
    for (int next : getNextStates(state)) {
        if (!/* 범위 검사 조건 */) {
            continue;
        }

        if (!/* 유효성 검사 */) {
            continue;
        }

        // 중복 검사
        if (isVisited[state]) {
            continue;
        }

        // 방문 처리
        isVisited[state] = true;
        queue.add(next);
    }
}