[알고리즘 공부] #7 너비 우선 탐색(BFS) 알고리즘 with Python

[알고리즘 공부] #6 연결 리스트(Linked List) 알고리즘 with Python

[알고리즘 공부] #6 연결 리스트(Linked List) 알고리즘 with Python

이전 알고리즘 글 읽기

큐 알고리즘(Queue)

어떤 알고리즘일까?

너비 우선 탐색(BFS)란 트리나 그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘이다. 모든 인접한 노드를 큐(Queue)에 넣고 탐색하는 방식이다. 탐색은 레벨별(너비 우선)로 진행된다.

BFS 너비 우선 탐색 설명 그림

위에 사진을 보면 이해하기 쉽다. 0을 시작 노드라고 가정했을 때, 인접한 노드인 1과 2를 먼저 탐색하는 것을 알 수 있다.(레벨별로 탐색하는 것도 알 수 있다.)

---

너비 우선 탐색 장단점

• 장점
  1. 최단 경로 탐색에 적합 : 가중치가 없는 그래프에서 시작 노드로부터 특정 노드까지의 최단 경로를 찾을 수 있다.
  2. 레벨별 탐색 : 탐색 순서를 보장하기 때문에 트리나 그래프에서 각 레벨에 해당하는 노드를 분석하기에 좋다.
  3. 올바른 탐색 보장 : 이미 방문한 노드를 다시 방문하지 않으므로 불필요한 반복이 없다.
• 단점
  1. 메모리 소모 : 모든 노드를 큐에 저장하기 때문에, 노드가 많을수록 메모리 사용량이 증가한다.
  2. 가중치가 있는 그래프에 부적합 : 가중치가 있는 그래프에서 최단 경로를 찾을 수 없다.(이 경우 다익스트라 알고리즘을 사용함)
  3. 노드 수에 비례한 속도 : 그래프가 크면 BFS의 탐색 시간이 오래 걸릴 수 있다.

---

언제 사용하는가?

• 최단 경로 탐색 : BFS는 모든 간선의 가중치가 동일할 때, 출발지에서 특정 노드까지의 최다 경로를 찾는 데 유용하다.
• 최소 비용 문제 : 미로 탈출, 전염병 퍼지는 시간 계산 등의 문제에서 사용된다.
• 모든 정점을 레벨별로 탐색 : 노든 간의 관계를 레벨별로 분석할 때 사용한다.
• 최소 횟수로 특정 상태에 도달 : 상태 전이를 최소화하면서 목표 상태에 도달하는 문제.

---

시간 복잡도

• 시간 복잡도 : O(V + E)
  • V : 정점의 수
  • E : 간선의 수
  • 모든 정점을 방문하며, 각 간선을 검사하기 때문이다.
• 공간 복잡도 : O(V) (큐에 저장되는 노드의 수)

---

BFS 알고리즘 동작 과정

1. 탐색 시작 노드를 큐에 추가한다.
2. 큐에서 노드를 하나 꺼내 방문한다.
3. 방문한 노드의 **인접 노드(자식 노드)**를 큐에 추가한다.
4. 큐가 비어있을 때까지 과정을 반복한다.

---

BFS 구현

def bfs(graph, node, visited):
    # BFS구현을 위한 Queue 이용
    queue = [node]
    # 현재 노드 방문 처리
    visited[node] = True

    #큐가 빌 때까지 반복
    while queue:
        # 큐에 삽인된 순서대로 노드 꺼내기
        v = queue.pop(0)
        print(v, end = ' ')
        # 현재 노드를 기준으로 방문하지 않은 인접 노드 큐에 삽입
        for i in graph[v]:
            if not (visited[i]):
                queue.append(i)
                visited[i] = True

# 임시 그래프 생성
graph = [
    [],
    [2, 3],
    [1, 8],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7, 8],
    [6, 8],
    [2, 6, 7]
]

# 방문 정보를 체크하기 위한 리스트
visited = [False] * 9

# 함수 호출
bfs(graph, 1, visited)

위에 코드처럼 간단하게 BFS를 구현할 수 있다.

먼저 기준 노드를 큐에 삽입한 후, 현재 노드를 기준으로 방문하지 않은 인접 노드를 모두 큐에 삽입한다.(방문한 노드는 항상 방문 처리를 해줘야 한다.)

그 후 큐가 빌 때까지, 즉 모든 노드를 방문할 때까지 이 과정을 반복한다.

실제 문제에서는, 입력값(graph)도 트리로 구현해야 한다.

---

알고리즘 관련 예제

백준 : 숨바꼭질 (S1)

https://www.acmicpc.net/problem/1697

from collections import deque

class Node:
    def __init__(self, val):
        self.val = val
        self.double = None
        self.plus = None
        self.minus = None

class Graph:
    def __init__(self, data, K):
        self.root = Node(data)
        self.queue = deque()
        self.visited = set()
        for next_val in (self.root.val * 2, self.root.val + 1, self.root.val - 1):
            if next_val >= 0 and next_val <= 100000 and next_val not in self.visited:
                self.queue.append(next_val)
                self.visited.add(next_val)

    def bfs(self, K):
        queue = self.queue
        visited = self.visited
        level = 1
        check = queue[-1]
        while queue:
            curr_node = queue.popleft()
            if curr_node == K:
                return level
            
            for next_val in (curr_node * 2, curr_node + 1, curr_node - 1):
                if next_val >= 0 and next_val <= 100000 and next_val not in visited:
                    queue.append(next_val)
                    visited.add(next_val)

            if curr_node == check:
                level += 1
                check = queue[-1]

N, K = map(int,input().split())
headRoot = Graph(N, K)

if N == K:
    print(0)
else:
    print(headRoot.bfs(K))

deque 라이브러리를 가져와 큐를 구현해주었으며, bfs를 사용하는 가장 기본적인 방식의 문제이다.

탐색할 수 있는 노드를 레벨 별로(너비 우선으로) 탐색하며 가장 빠른 경로를 찾는다는 점에서 BFS를 만족시킨다.

 

살짝 고생했던 점은 조건에 맞춰 방문 처리를 더 확실하게 해주지 않아 시간 초과 오류가 발생한 점이다.

결국은 조건에 맞춰 탐색하지 않아도 될 값을 탐색하지 않게 설정해주었고, 최종적으로 문제를 풀 수 있었다.

 

참고로 실전에서는 class로 구현할 필요 없이 bfs 함수를 만들어 푸는 것이 일반적이다.

(알고리즘을 제대로 이해하기 위해서 class로 구현하였다.)

---