DFS, BFS Template

 

🧭 DFS / BFS 정복 세트

---

🧩 1️⃣ DFS 완전 암기용 버전

📘 기본 그래프형 (재귀 DFS)

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

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

패턴 암기 포인트

• “방문하고 → 다음으로 간다”
• 재귀함수 종료조건은 별도 필요 없음 (자연스럽게 if로 걸러짐)
• 스택을 쓰는 DFS는 거의 동일하지만 명시적으로 스택만 씀

---

📗 2차원 배열형 (미로, 섬 개수, 영역 탐색 등)

static void dfs(int x, int y) {
    visited[x][y] = true;

    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d];
        int ny = y + dy[d];

        if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
        if (!visited[nx][ny] && map[nx][ny] == 1) {
            dfs(nx, ny);
        }
    }
}

핵심

• visited 먼저 체크
• 범위체크 → 방문체크 → 조건확인 순서
• map[nx][ny] == 1 같은 조건은 문제에 따라 다름

---

⚙️ dx, dy 기본 세트 (4방 / 8방)

// 4방향 (상하좌우)
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};

// 8방향 (대각선 포함)
int[] dx8 = {-1,-1,-1, 0, 0, 1, 1, 1};
int[] dy8 = {-1, 0, 1,-1, 1,-1, 0, 1};

---

🚀 2️⃣ BFS 완전 암기용 버전

📘 기본 그래프형 (큐 BFS)

Queue<Integer> q = new LinkedList<>();
q.add(start);
visited[start] = true;

while (!q.isEmpty()) {
    int cur = q.poll();

    for (int next : graph[cur]) {
        if (!visited[next]) {
            visited[next] = true;
            q.add(next);
        }
    }
}

패턴 암기 포인트

• “큐에 넣을 때 방문 체크”
• poll → 탐색 → add 구조
• 거리계산 시 배열 추가 (dist[next] = dist[cur] + 1)

---

📗 2차원 배열형 (미로 탐색, 최단거리 등)

Queue<int[]> q = new LinkedList<>();
q.add(new int[]{sx, sy});
visited[sx][sy] = true;

while (!q.isEmpty()) {
    int[] cur = q.poll();
    int x = cur[0];
    int y = cur[1];

    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d];
        int ny = y + dy[d];

        if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
        if (!visited[nx][ny] && map[nx][ny] == 1) {
            visited[nx][ny] = true;
            q.add(new int[]{nx, ny});
        }
    }
}

---

🧠 DFS vs BFS 비교 요약표

항목 DFS BFS

탐색 구조	재귀 or 스택	큐
탐색 순서	한 경로 끝까지	가까운 노드부터
주 사용 목적	경로 탐색, 백트래킹	최단거리 탐색
방문 체크 시점	재귀 진입 직전	큐에 넣을 때
시간 복잡도	O(V + E)	O(V + E)
사용 예시	섬의 개수, 연결 요소	미로 탐색, 최소 거리

---

🎯 문제유형별 추천 템플릿 선택표

문제 유형 예시 문제 추천 알고리즘 설명

미로 탐색	2178	BFS	최단거리 구하기
바이러스 전파	2606	DFS/BFS	연결된 컴퓨터 수
섬의 개수	4963	DFS(8방향)	영역 탐색
단지 번호 붙이기	2667	DFS	영역 개수 세기
토마토	7576	BFS	익는 시간 (다중 시작점)
숨바꼭질	1697	BFS	최소 이동 횟수
유기농 배추	1012	DFS/BFS	영역 탐색
촌수 계산	2644	DFS/BFS	두 노드 간 거리 계산
미로 탈출	2178	BFS	최단 경로 길이 계산
양과 늑대	3184	DFS	영역 내 조건 계산

---

📚 백돌이의 암기 팁

• 🔹 “DFS는 깊이, BFS는 거리”
• 🔹 DFS는 스택 or 재귀, BFS는 큐
• 🔹 2차원 문제는 항상 dx, dy 세트 먼저 선언
• 🔹 방문 순서가 중요하면 BFS,
  탐색 범위가 중요하면 DFS