알고리즘 03 - (기본 패턴 02) - (4) 그래프 탐색, BFS (너비 우선 탐색, Breadth-First Search) - BFS와 슬라이딩 윈도우의 차이

그래프 탐색: BFS와 슬라이딩 윈도우의 차이

BFS(너비 우선 탐색)와 슬라이딩 윈도우는 둘 다 특정 문제를 해결하기 위한 알고리즘적 접근 방식이지만, 작동 원리와 사용 목적은 다릅니다.
BFS는 그래프 탐색 알고리즘, 슬라이딩 윈도우는 구간 처리 기법입니다.

---

BFS의 이동 방식

BFS에서 이동은 큐(Queue)를 사용하여 이루어지며, 그래프 구조에서 노드 간의 연결을 따라가며 탐색합니다.
탐색 과정은 다음과 같이 진행됩니다:

1. 시작 노드를 큐에 추가.
2. 큐에서 노드를 꺼내 방문.
3. 꺼낸 노드의 인접 노드(연결된 노드)를 큐에 추가.
4. 큐가 비어 있을 때 탐색 종료.

이동 방식은 연결된 노드를 따라 진행하며, 탐색 대상이 되는 노드들이 큐에 저장됩니다.
탐색 순서는 큐의 FIFO(First-In, First-Out) 특성을 따릅니다.

---

슬라이딩 윈도우의 이동 방식

슬라이딩 윈도우는 주로 배열이나 문자열의 연속된 구간을 처리할 때 사용됩니다.
윈도우의 크기를 고정하거나 가변적으로 설정하고, 윈도우를 이동하면서 필요한 값을 계산합니다.

1. 윈도우가 초기 구간을 처리.
2. 윈도우를 한 칸 이동.
3. 윈도우 내 데이터를 업데이트.
4. 전체 구간을 처리할 때까지 반복.

---

BFS와 슬라이딩 윈도우의 주요 차이점

특징	BFS	슬라이딩 윈도우
데이터 구조	큐(Queue)를 사용	구간의 시작과 끝을 이동 (인덱스 활용)
작동 대상	그래프의 노드 및 간선 탐색	배열이나 문자열의 연속된 데이터 구간
목적	그래프에서 연결된 노드 탐색	구간 내의 값을 효율적으로 계산
이동 방식	노드와 인접 노드 간의 연결을 따라 탐색	윈도우를 한 칸씩 이동하며 구간 처리
적용 예시	최단 경로 탐색, 연결 컴포넌트 찾기	최대/최소 부분합, 특정 패턴 찾기

---

BFS의 이동 예시

그래프

graph = {1: [2, 3], 2: [4], 3: [5], 4: [], 5: []}

BFS 코드

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            print(f"방문한 노드: {node}")
            queue.extend(graph[node])

bfs(graph, 1)

출력

방문한 노드: 1
방문한 노드: 2
방문한 노드: 3
방문한 노드: 4
방문한 노드: 5

BFS 이동 과정

1. 큐: [1] → 방문 1.
2. 큐: [2, 3] → 방문 2.
3. 큐: [3, 4] → 방문 3.
4. 큐: [4, 5] → 방문 4.
5. 큐: [5] → 방문 5.

---

슬라이딩 윈도우의 이동 예시

문제: 배열에서 길이가 3인 부분 배열의 합 계산

nums = [1, 3, 5, 7, 9]
k = 3

# 슬라이딩 윈도우로 부분 합 계산
window_sum = sum(nums[:k])  # 첫 윈도우 합
print(f"초기 윈도우 합: {window_sum}")

for i in range(k, len(nums)):
    window_sum += nums[i] - nums[i - k]  # 윈도우 이동
    print(f"윈도우 이동 후 합: {window_sum}")

출력

초기 윈도우 합: 9
윈도우 이동 후 합: 15
윈도우 이동 후 합: 21
윈도우 이동 후 합: 27

슬라이딩 윈도우 이동 과정

1. 초기 윈도우: [1, 3, 5] → 합: 9.
2. 윈도우 이동: [3, 5, 7] → 합: 15.
3. 윈도우 이동: [5, 7, 9] → 합: 21.

---

BFS와 슬라이딩 윈도우를 구분하는 팁

1. 데이터 구조를 확인:
   • BFS: 큐를 사용하여 그래프의 노드를 순차적으로 탐색.
   • 슬라이딩 윈도우: 배열이나 문자열의 연속된 구간을 탐색.
2. 탐색 대상의 특성:
   • BFS: 그래프(노드, 간선)의 연결 관계를 탐색.
   • 슬라이딩 윈도우: 연속된 데이터 구간을 처리.
3. 이동 방식의 차이:
   • BFS: 인접 노드를 큐에 추가하며 탐색.
   • 슬라이딩 윈도우: 구간의 시작과 끝을 이동하며 처리.

---

결론

• BFS는 큐를 사용해 그래프의 연결된 노드를 탐색하는 알고리즘입니다.
• 슬라이딩 윈도우는 배열이나 문자열의 특정 구간을 이동하며 처리하는 기법입니다.
• BFS와 슬라이딩 윈도우는 서로 다른 문제를 해결하기 위해 사용되며, 탐색 대상과 이동 방식이 다릅니다.