📌 DFS/BFS이란?

DFS

DFS(node)
① DFS(Depth-First Search, 깊이우선탐색)는 시작 노드에서 한 방향의 끝까지 탐색 후, 다시 되돌아와 다른 경로를 탐색하는 방식이다.

그래서 다시 돌아오는 형질이 있기 때문에 '스택(Stack)' 자료구조나 '재귀 함수'를 사용해야 한다. 완전 탐색과같은 특징을 파악해야 한다.

BFS

Queue<Integer> queue = new LinkedList<>();
② BFS (Breadth-First Search, 너비 우선 탐색)는 시작 노드에서 가까운 노드부터 방문하는 넓에 퍼져나가는 탐색 방식이다.

그래서 FIFO 방식인 큐(Queue) 자료구조를 사용해야 한다. 최단 경로를 구할 때 주용 사용된다.

✅ 정점의 수를 V, 간선의 수를 E라고 할 때, 두 알고리즘 모두

• 인접 리스트 방식을 사용하면 O(V+E)
• 인접 행렬 방식을 사용하면 O(V²)

의 시간이 소요된다.

1️⃣ 대표적인 문제

2️⃣ DFS 문제 공식

언제 DFS를 의심할까?
문제에 이런 단어가 보이면 DFS 가능성이 높다.

• 모든 경우의 수
• 가능한 모든 경로
• 조합
• 순열
• 백트래킹

📌 DFS는 크게 2가지로 나뉜다.
1️⃣ 그래프 DFS (네트워크/연결 요소 찾기/트리 탐색)

void dfs(int node){
    visited[node] = true;

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

2️⃣ 완전탐색 DFS(타겟 넘버/N-Queen/순열/조합/피로도)

dfs(depth + 1);
dfs(depth + 1);

< DFS 사고 과정 >

✅ STEP 1. 현재 상태 정의
현재 내가 무엇을 탐색하고 있는가?

예)

타겟 넘버
→ 현재 인덱스, 현재 합

N-Queen
→ 현재 행

순열
→ 현재 선택 개수

✅ STEP 2. 종료 조건 정의

if(종료조건){
    return;
}

예) if(idx == numbers.length)

✅ STEP 3. 다음 상태 탐색
dfs(다음상태);
가능한 모든 선택지를 재귀 호출한다.

✅ STEP 4. 방문 안 했으면 재귀

if(!visited[next]){
    dfs(next);
}

2️⃣ BFS 문제 공식

언제 BFS를 의심할까?
문제에 이런 단어가 보이면 BFS 가능성이 높다.

• 최단 거리
• 최소 이동 횟수
• 가장 빨리 도착
• 몇 번 만에 도달

Queue<Integer> queue = new LinkedList<>();

queue.offer(start);
visited[start] = true;

while(!queue.isEmpty()){

    int now = queue.poll();

    for(int next : graph[now]){

        if(!visited[next]){

            visited[next] = true;
            queue.offer(next);
        }
    }
}

< BFS 사고 과정>

✅ STEP 1. 시작점 Queue 삽입

queue.offer(start);

✅ STEP 2. 방문 처리

visited[start] = true;

✅ STEP 3. Queue에서 꺼내기

int now = queue.poll();

✅ STEP 4. 다음 노드 확인

for(int next : graph[now])

✅ STEP 5. 방문 안 했으면 Queue 삽입

if(!visited[next]){
    visited[next] = true;
    queue.offer(next);
}

⚠️ DFS/BFS 문제의 핵심

DFS/BFS에서 가장 중요한 것은 중복 방문 방지이다.

이미 방문한 노드를 다시 탐색하면 무한 루프에 빠질 수 있기 때문에 방문 배열을 사용한다.

boolean[] visited = new boolean[n + 1];

혹은

boolean[][] visited = new boolean[n][m];

와 같이 관리한다.

3️⃣ 그리디 알고리즘 문제

• 프로그래머스
  DFS/BFS 문제 정리 사이트
  
• LeetCode
  LeetCode DFS Problem List
  LeetCode BFS Problem List