🔍 BFS vs DFS

GNN공부하러왔다가 봉변 맞기
-> 맨날 푸는 BFS, DFS 또 틀리다~

진짜 BFS, DFS 문제는 좀만 복잡해져도 무한 틀림임~

저는 코테 가기전에는 꼭 간단한 예제로 외워서 적용하자! 라는 마인드로 가요

항목	BFS (Breadth-First Search)	DFS (Depth-First Search)
탐색 방식	가까운 노드부터 차례대로 탐색	깊은 노드부터 끝까지 탐색 후 되돌아옴
자료구조	큐 (Queue)	스택(Stack) or 재귀(Recursion)
사용 예시	최단 거리, 퍼짐 현상 등	영역 탐색, 조합 탐색, 경로 존재 여부
구현 난이도	비교적 쉬움	재귀 호출에 익숙해야 함
대표 예제	미로에서 최단 경로	얼음 덩어리 개수 세기

---

✅ BFS 문제: 미로 탈출

문제 설명

N x M 크기의 미로가 0과 1로 이루어져 있습니다.

• 1은 이동 가능한 길, 0은 벽입니다.
• (0, 0)에서 출발하여 (N-1, M-1)까지 최단 거리로 이동할 때 지나야 하는 칸의 수를 구하세요.
• 상하좌우로만 이동 가능합니다.

예제 입력

5 6
101010
111111
000001
111111
111111

예제 출력

10

---

풀이 코드 (BFS)

from collections import deque

def bfs_maze_escape(maze):
    n = len(maze)
    m = len(maze[0])
    visited = [[False]*m for _ in range(n)]

    dx = [-1, 1, 0, 0]  # 상하좌우
    dy = [0, 0, -1, 1]

    queue = deque()
    queue.append((0, 0))
    visited[0][0] = True

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                if maze[nx][ny] == 1:
                    queue.append((nx, ny))
                    visited[nx][ny] = True
                    maze[nx][ny] = maze[x][y] + 1  # 이전 칸 거리 + 1

    return maze[n-1][m-1]

🧠 함수 설명

• visited: 이미 방문한 노드를 다시 방문하지 않기 위한 체크.
• queue: BFS 탐색을 위한 큐.
• maze[x][y] = maze[x][y] + 1: 최단 거리 누적.

---

✅ DFS 문제: 얼음 얼리기

문제 설명

N x M 크기의 얼음 틀에서

• 0: 얼음이 생성될 수 있는 칸
• 1: 벽

상하좌우로 연결된 0 묶음을 얼음 1개로 본다면, 전체 얼음 덩어리는 몇 개인가요?

예제 입력

4 5
00110
00011
11111
00000

예제 출력

3

---

풀이 코드 (DFS)

def dfs(x, y, graph):
    n = len(graph)
    m = len(graph[0])

    if x < 0 or x >= n or y < 0 or y >= m:
        return False
    if graph[x][y] == 0:
        graph[x][y] = 1  # 방문 처리
        dfs(x-1, y, graph)
        dfs(x+1, y, graph)
        dfs(x, y-1, graph)
        dfs(x, y+1, graph)
        return True
    return False

def count_ice_areas(graph):
    n = len(graph)
    m = len(graph[0])
    count = 0

    for i in range(n):
        for j in range(m):
            if dfs(i, j, graph):
                count += 1
    return count

🧠 함수 설명

• dfs: 현재 위치에서 인접한 0을 재귀적으로 탐색.
• 한 번의 DFS 호출 = 얼음 1덩어리 탐색 완료.
• 방문한 위치는 1로 바꿔 재탐색 방지.

---

각 코드에서

DFS가 쓰이는 이유

👉 "끝까지 들어가서 하나의 연결된 덩어리를 다 보고 나오는 방식"이 필요할 때
예: 연결된 구역, 조합, 경로 존재 여부 등

"갈 수 있을 만큼 깊이 파고들어, 전체를 한 번에 확인하고 온다."

---

BFS가 쓰이는 이유

👉 "가장 가까운 경로를 먼저 탐색하고, 단계별로 넓혀가는 방식"이 필요할 때
예: 최단 거리, 최소 횟수, 레벨 탐색 등

"한 칸씩, 가까운 곳부터 차례대로 탐색해서 가장 빠른 길을 찾는다."

---

🎯 핵심 비교 한 줄 요약

• DFS는 "끝까지 파고들며 탐색해야 할 때"
• BFS는 "가장 빠른 길(최단 거리)을 찾을 때"