DFS 복습하기

DFS란?

Depth-First Search | 깊이 우선 탐색
모든 가능한 경로를 끝까지 탐색하는 재귀적 방식

예를 들어, 미로에서 출구를 찾는다고 하면 한 방향으로 쭉 들어가고, 막히면 돌아와서 다른 방향을 탐색하는 방식!

구조 핵심 요약

void dfs(현재위치, 상태) {
    if (목표 도달) return;

    for (다음위치) {
        if (조건 만족) {
            dfs(다음위치, 갱신된 상태);
        }
    }
}

DFS 탐색 순서

스택(Stack) 구조처럼 작동.
즉 깊이를 따라 재귀적으로 탐색하고, 더 이상 갈 곳이 없으면 되돌아가서 다른 경로를 탐색하는 방식

DFS 기본 성질

• 재귀함수 or Stack 사용 가능
• 모든 경우의 수를 탐색할 때 적합 (경로 탐색, 완전 탐색 등)
• 방문 체크 배열을 함께 쓰는 경우가 많음 (무한 루프 방지를 위해서)
• 시간복잡도는 그래프에 따라 다르지만, 일반적으로 O(V + E) (노드 + 간선)

DFS vs BFS

구분	DFS (깊이 우선)	BFS (너비 우선)
구조	재귀 / 스택	큐 (Queue)
순서	한 경로 끝까지	가까운 곳부터
사용처	모든 경로 탐색, 백트래킹	최단 거리, 레벨 탐색
예시	미로 경로 찾기, 퍼즐 조합	미로 최단거리, 최단 경로

DFS 주요 사용 예시

• 모든 경로 / 조합 / 순열 탐색
• 미로 문제
• 백트래킹
• 그래프 연결 요소 개수
• 섬의 개수, 영역 구분 문제
• 트리 순회

실수 포인트

• 종료 조건 누락 -> 무한 재귀
• 방문 체크 누락 -> 무한 루프
• 매번 새로운 상태 계산이 필요한 경우 -> 복사 or 매개변수 전달 활용

예시 코드

public class MazeDFS {
    static int[][] maze = {
        {1, 1, 0, 1},
        {0, 1, 1, 0},
        {0, 0, 1, 1},
        {1, 1, 1, 1}
    };
    static boolean[][] visited = new boolean[4][4];
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};

    public static void main(String[] args) {
        dfs(0, 0);
    }

    public static void dfs(int y, int x) {
        int N = maze.length, M = maze[0].length;

        // 범위 벗어나거나 방문했거나 벽이면 return
        if (y < 0 || y >= N || x < 0 || x >= M) return;
        if (visited[y][x] || maze[y][x] == 0) return;

        visited[y][x] = true;
        System.out.println("Visited: (" + y + ", " + x + ")");

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            dfs(ny, nx);
        }
    }
}

---

BFS 문제 추천

🧱 [기초 감 잡기] - BFS 개념 익히기

No.	문제명	난이도	링크
1	미로 탐색 (2178)	Silver 1	🔗
2	숨바꼭질 (1697)	Silver 1	🔗
3	촌수 계산 (2644)	Silver 2	🔗
4	DFS와 BFS (1260)	Silver 2	🔗

🏃 [중간 단계] - 다양한 그래프 응용

No.	문제명	난이도	링크
5	나이트의 이동 (7562)	Silver 1	🔗
6	토마토 (7576)	Gold 5	🔗
7	불! (4179)	Gold 4	🔗

🌊 [응용 + 최단거리 + 멀티 시작점]

No.	문제명	난이도	링크
8	벽 부수고 이동하기 (2206)	Gold 4	🔗
9	알고스팟 (1261)	Gold 4	🔗
10	이모티콘 (14226)	Gold 5	🔗
11	탈출 (3055)	Gold 5	🔗