1. BFS(너비 우선 탐색): 그래프 탐색 알고리즘의 핵심 이해하기

이미지 출처 - https://skilled.dev/course/breadth-first-search

"모든 길을 가장 효율적으로 탐색하는 방법을 찾는 것은 알고리즘의 핵심 과제입니다. BFS는 마치 물결이 퍼지듯 가까운 곳부터 체계적으로 탐색하는 방법을 제공합니다."

목차

• BFS란 무엇인가?
• BFS vs DFS: 핵심 차이점
• BFS의 동작 원리
• 시간 복잡도 분석
• 필요한 자료구조
• 실전 문제 분석: 백준 1926번
• 코드 구현 단계별 가이드
• 최적화 전략과 주의사항
• 학습 전략 및 추천 문제
• 결론

---

BFS란 무엇인가?

BFS(Breadth-First Search, 너비 우선 탐색)는 그래프나 트리 구조에서 모든 노드를 효율적으로 방문하기 위한 알고리즘입니다. 시작 노드에서부터 가까운 노드를 먼저 방문하고, 멀리 있는 노드를 나중에 방문하는 방식으로 동작합니다.

그래프 탐색의 기본 개념

그래프 탐색은 연결된 모든 노드를 체계적으로 방문하는 과정입니다. 이를 통해 다음과 같은 작업을 수행할 수 있습니다:

• 특정 노드 찾기 (예: 미로에서 출구 찾기)
• 연결된 요소의 개수 세기 (예: 그림 영역의 개수)
• 모든 노드 방문하며 정보 수집 (예: 네트워크 패킷 전송)

그래프 구성 요소

그래프는 다음 두 가지 핵심 요소로 구성됩니다:

1. Vertex(정점): 탐색의 대상이 되는 개체
2. Edge(간선): 정점 간의 연결 관계

실생활에서 그래프는 도로망, 소셜 네트워크, 전자 회로 등 다양한 시스템을 모델링하는 데 사용됩니다.

---

BFS vs DFS: 핵심 차이점

BFS와 DFS는 그래프 탐색의 두 가지 주요 방법으로, 서로 다른 접근 방식을 가집니다:

특성	BFS (너비 우선 탐색)	DFS (깊이 우선 탐색)
탐색 방식	레벨 단위로 탐색	한 경로를 끝까지 탐색
자료구조	큐(Queue)	스택(Stack) 또는 재귀
메모리	일반적으로 더 많이 사용	일반적으로 더 적게 사용
최단 경로	최단 경로 보장 (가중치 없는 그래프)	최단 경로 보장하지 않음
무한 그래프	무한 그래프에서 문제 발생 가능	무한 그래프에서도 사용 가능

탐색 순서 비교

다음과 같은 그래프가 있을 때:

    1
   / \
  2   5
 / \
3   4
     \
      6

• BFS 탐색 순서: 1 → 2, 5 → 3, 4 → 6
  • 레벨 별로 탐색: 시작 노드(Level 0) → 인접 노드(Level 1) → 인접 노드의 인접 노드(Level 2)...
• DFS 탐색 순서: 1 → 2 → 3 → 4 → 6 → 5
  • 한 경로를 끝까지 탐색한 후 다음 경로 탐색

---

BFS의 동작 원리

BFS는 큐(Queue) 자료구조를 활용하여 구현됩니다. 먼저 들어온 노드가 먼저 처리되는 FIFO(First In First Out) 방식을 따릅니다.

BFS 알고리즘의 기본 단계

1. 시작 노드를 큐에 넣고 방문 처리합니다.
2. 큐에서 노드를 꺼내고, 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 넣고 방문 처리합니다.
3. 큐가 빌 때까지 2번 과정을 반복합니다.

BFS 동작 예시

앞서 본 그래프에서 BFS 동작을 단계별로 살펴보겠습니다:

1. 노드 1을 큐에 넣고 방문 처리
   • 큐: [1], 방문: {1}
2. 큐에서 1을 꺼내고 인접 노드 2, 5를 큐에 넣음
   • 큐: [2, 5], 방문: {1, 2, 5}
3. 큐에서 2를 꺼내고 인접 노드 3, 4를 큐에 넣음
   • 큐: [5, 3, 4], 방문: {1, 2, 5, 3, 4}
4. 큐에서 5를 꺼냄 (인접한 미방문 노드 없음)
   • 큐: [3, 4], 방문: {1, 2, 5, 3, 4}
5. 큐에서 3을 꺼냄 (인접한 미방문 노드 없음)
   • 큐: [4], 방문: {1, 2, 5, 3, 4}
6. 큐에서 4를 꺼내고 인접 노드 6을 큐에 넣음
   • 큐: [6], 방문: {1, 2, 5, 3, 4, 6}
7. 큐에서 6을 꺼냄 (인접한 미방문 노드 없음)
   • 큐: [], 방문: {1, 2, 5, 3, 4, 6}

큐가 비었으므로 BFS 탐색이 완료됩니다.

---

시간 복잡도 분석

BFS의 시간 복잡도는 그래프의 표현 방식과 크기에 따라 달라집니다.

일반적인 시간 복잡도

• 인접 리스트 사용 시: O(V + E)
• 인접 행렬 사용 시: O(V²)

여기서:

• V는 정점(Vertex)의 개수
• E는 간선(Edge)의 개수

시간 복잡도 분석 이유

알고리즘 효율성을 판단하고 최적화하기 위해 시간 복잡도 분석이 필수적입니다. 특히 경쟁 프로그래밍이나 대규모 데이터를 다루는 상황에서는 시간 제한 내에 문제를 해결해야 하므로 알고리즘의 효율성이 중요합니다.

문제의 입력 크기에 따라 시간 복잡도를 계산하여 해당 알고리즘이 시간 제한 내에 동작할 수 있는지 판단할 수 있습니다.

---

필요한 자료구조

BFS 구현을 위해 다음과 같은 자료구조가 필요합니다:

1. 그래프 표현 (2가지 방법)

인접 행렬 (Adjacency Matrix)

# n개의 노드가 있는 그래프 표현
graph = [[0] * (n + 1) for _ in range(n + 1)]

# 노드 1과 2가 연결되어 있다면
graph[1][2] = 1
graph[2][1] = 1  # 양방향 그래프의 경우

인접 리스트 (Adjacency List)

# n개의 노드가 있는 그래프 표현
graph = [[] for _ in range(n + 1)]

# 노드 1과 2가 연결되어 있다면
graph[1].append(2)
graph[2].append(1)  # 양방향 그래프의 경우

2. 방문 여부 체크 배열

# 1차원 그래프의 경우
visited = [False] * (n + 1)

# 2차원 그래프(격자)의 경우
visited = [[False] * m for _ in range(n)]

3. BFS를 위한 큐

파이썬에서는 collections 모듈의 deque를 사용하면 효율적입니다:

from collections import deque

queue = deque()
queue.append(start_node)  # 시작 노드 추가

---

실전 문제 분석: 백준 1926번

백준 1926번 - 그림은 BFS의 기본 개념을 활용하는 대표적인 문제입니다.

문제 요약

• 2차원 배열에서 1은 그림의 일부, 0은 빈 공간을 의미
• 그림은 상하좌우로 연결된 1들의 집합
• 두 가지를 출력:
  1. 그림의 개수
  2. 가장 넓은 그림의 넓이 (1의 개수)

접근 방법

1. 2차원 배열의 모든 칸을 순회하며 값이 1이고 아직 방문하지 않은 칸을 시작점으로 BFS 수행
2. BFS를 시작할 때마다 그림 개수 증가
3. 각 BFS 실행 시 연결된 모든 1의 개수(그림의 넓이)를 세고, 최대값 갱신

문제 해결 아이디어 시각화

예를 들어, 다음과 같은 입력이 있다고 가정해봅시다:

1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
1 0 1 1 1

여기서는 세 개의 그림이 있으며, 크기는 각각 3, 1, 9입니다.

BFS를 통해 첫 번째 그림을 탐색하는 과정을 시각화하면 다음과 같습니다:

1. (0,0)에서 시작: 큐 = [(0,0)], 방문 = {(0,0)}, 크기 = 1
2. (0,0)의 인접 칸 중 (0,1)을 큐에 추가: 큐 = [(0,1)], 방문 = {(0,0), (0,1)}, 크기 = 2
3. (0,1)의 인접 칸 중 (1,1)을 큐에 추가: 큐 = [(1,1)], 방문 = {(0,0), (0,1), (1,1)}, 크기 = 3
4. (1,1)의 인접 칸 중 방문하지 않은 1이 없으므로 BFS 종료, 크기 = 3

이런 식으로 모든 그림을 찾아 개수와 최대 크기를 계산합니다.

---

코드 구현 단계별 가이드

BFS를 활용한 백준 1926번 문제의 해결 과정을 단계별로 살펴보겠습니다.

1. 기본 설정

from collections import deque
import sys
input = sys.stdin.readline  # 빠른 입력을 위한 설정

# 그래프의 크기 입력 받기
n, m = map(int, input().split())
# 그래프 정보 입력 받기
graph = [list(map(int, input().split())) for _ in range(n)]
# 방문 여부 체크 배열 초기화
visited = [[False] * m for _ in range(n)]

# 상, 우, 하, 좌 방향 벡터 (상하좌우 이동을 위한 좌표 변화량)
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

2. BFS 함수 구현

def bfs(y, x):
    q = deque()
    q.append((y, x))
    visited[y][x] = True
    size = 1  # 현재 그림의 크기 (시작점 포함)

    while q:
        ey, ex = q.popleft()
        for k in range(4):
            ny, nx = ey + dy[k], ex + dx[k]
            # 범위 체크
            if 0 <= ny < n and 0 <= nx < m:
                # 그림의 일부이고 아직 방문하지 않았다면
                if graph[ny][nx] == 1 and not visited[ny][nx]:
                    visited[ny][nx] = True
                    q.append((ny, nx))
                    size += 1
    return size  # 그림의 크기 반환

3. 전체 그래프 탐색

cnt = 0  # 그림의 개수
max_size = 0  # 가장 큰 그림의 크기

for y in range(n):
    for x in range(m):
        # 그림의 일부이고 아직 방문하지 않았다면 BFS 수행
        if graph[y][x] == 1 and not visited[y][x]:
            cnt += 1  # 그림 개수 증가
            max_size = max(max_size, bfs(y, x))  # 최대 크기 갱신

print(cnt)  # 그림의 개수 출력
print(max_size)  # 가장 큰 그림의 크기 출력

전체 코드

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs(y, x):
    q = deque()
    q.append((y, x))
    visited[y][x] = True
    size = 1

    while q:
        ey, ex = q.popleft()
        for k in range(4):
            ny, nx = ey + dy[k], ex + dx[k]
            if 0 <= ny < n and 0 <= nx < m:
                if graph[ny][nx] == 1 and not visited[ny][nx]:
                    visited[ny][nx] = True
                    q.append((ny, nx))
                    size += 1
    return size

cnt = 0
max_size = 0

for y in range(n):
    for x in range(m):
        if graph[y][x] == 1 and not visited[y][x]:
            cnt += 1
            max_size = max(max_size, bfs(y, x))

print(cnt)
print(max_size)

---

최적화 전략과 주의사항

BFS 알고리즘을 효율적으로 구현하기 위한 몇 가지 전략과 주의사항을 살펴보겠습니다.

최적화 전략

1. 입출력 최적화: 대량의 입출력이 필요한 경우 Python의 sys.stdin.readline을 사용하여 입력 속도를 향상시킵니다.
2. 방문 체크 최적화: 큐에 노드를 넣을 때 방문 처리하는 것이 중요합니다. 큐에서 꺼낼 때 방문 처리하면 중복 방문으로 인한 시간 초과가 발생할 수 있습니다.
3. 메모리 사용 최적화: 필요한 경우에만 정보를 저장하고, 불필요한 정보는 버리는 것이 좋습니다.
4. 방향 벡터 활용: 상하좌우 이동을 위한 방향 벡터(dx, dy)를 미리 정의하여 코드 중복을 줄이고 가독성을 높입니다.

주의사항

1. 경계 체크: 항상 그래프의 경계를 벗어나지 않는지 체크해야 합니다.
2. if 0 <= nx < width and 0 <= ny < height: # 유효한 좌표인 경우에만 처리
3. 방문 여부 확인: 이미 방문한 노드는 다시 방문하지 않도록 방문 여부를 체크해야 합니다.
4. if not visited[ny][nx]: visited[ny][nx] = True queue.append((ny, nx))
5. 무한 루프 방지: 사이클이 있는 그래프에서 방문 체크를 하지 않으면 무한 루프에 빠질 수 있습니다.
6. 큐 오버플로 방지: 그래프가 매우 큰 경우, 큐의 크기가 매우 커질 수 있으므로 메모리 제한을 고려해야 합니다.

---

학습 전략 및 추천 문제

BFS 알고리즘을 완전히 이해하고 활용하기 위한 학습 전략을 소개합니다.

효과적인 학습 방법

1. 기본 구현 암기: BFS의 기본 구현 코드를 외워두면 문제 해결 시간을 단축할 수 있습니다.
2. 다양한 문제 풀이: 유사한 문제를 반복적으로 풀어 패턴을 이해하고 응용력을 키웁니다.
3. 코드 분석: 다른 사람의 효율적인 코드를 분석하여 다양한 구현 방법을 학습합니다.
4. 시각화 도구 활용: 알고리즘 시각화 도구를 활용하여 BFS 동작 과정을 직접 확인합니다.

BFS 관련 추천 문제

1. 백준 2178 - 미로 탐색
   • 최단 경로 찾기 문제로, BFS의 가장 기본적인 응용
2. 백준 7576 - 토마토
   • 여러 시작점에서 동시에 BFS를 수행하는 문제
3. 백준 2206 - 벽 부수고 이동하기
   • 상태를 추가한 BFS 문제 (벽을 부술 수 있는 기회가 있는 경우)
4. 백준 13549 - 숨바꼭질 3
   • 가중치가 다른 BFS 문제 (0-1 BFS)
5. 백준 2146 - 다리 만들기
   • BFS를 두 번 활용하는 문제

이러한 문제들을 단계적으로 풀어가며 BFS의 다양한 응용 방법을 익힐 수 있습니다.

---

결론

BFS(너비 우선 탐색)는 그래프 탐색의 기본이자 많은 문제 해결에 활용되는 강력한 알고리즘입니다. 큐를 사용하여 가까운 노드부터 탐색하는 BFS의 특성은 최단 경로 문제, 연결 요소 찾기, 레벨 단위 탐색 등 다양한 상황에서 유용하게 사용됩니다.

BFS의 핵심 요소 정리

1. 기본 원리: 가까운 노드부터 탐색하는 레벨 기반 접근법
2. 핵심 자료구조: 큐(Queue)를 사용하여 FIFO 방식으로 노드 처리
3. 시간 복잡도: O(V + E) (인접 리스트 사용 시)
4. 주요 응용 분야: 최단 경로 찾기, 연결 요소 탐색, 레벨 단위 분석

실무에서의 활용

BFS는 단순한 알고리즘 문제뿐만 아니라 실제 개발 현장에서도 널리 활용됩니다:

• 웹 크롤링: 웹 페이지를 순회하며 정보를 수집할 때
• 네트워크 분석: 소셜 네트워크에서 관계 분석할 때
• 추천 시스템: 유사한 아이템이나 사용자를 찾을 때
• AI 알고리즘: 게임의 최적 경로 찾기나 퍼즐 해결에 활용

그래프 탐색은 컴퓨터 과학의 기본 중의 기본이며, BFS는 그 중에서도 가장 중요한 알고리즘 중 하나입니다. 기본 원리를 정확히 이해하고 다양한 문제에 적용해보며 응용력을 키운다면, 알고리즘 역량이 크게 향상될 것입니다.

---

참고 자료

• Introduction to Algorithms (CLRS)
• 백준 온라인 저지 - 그래프 탐색 문제 모음
• 프로그래머스 코딩테스트 연습 - BFS/DFS
• 시각적으로 BFS를 이해하는 데 도움이 되는 사이트
• 파이썬 알고리즘 인터뷰 - 박상길 저