self.winter.(09-5). BFS (너비 우선 탐색) 개념 _ 백준 1260

🧐 너비 우선 탐색 ( Breadth First Search )

🤔 너비우선탐색, BFS란?

너비 우선 탐색, 즉 BFS는 그래프의 완전탐색(Exhaustive Search)기법 중 하나
- 너비 우선 탐색은 탐색 시작 노드와 가장 가까운 노드를 우선탐색한다.
- 이때, 목표노드에 도착하는 경로가 여러개라면, 최단경로를 보장한다.

BFS는 다음과 같은 특징이 있다.

기능	특징	시간복잡도 G(V, E)
그래프의 완전탐색 (Exhaustive Search)	Queue 자료구조를 이용한 FIFO 탐색	O(V+E)

BFS는 선입 선출 방식으로 탐색하는 방법이기에 큐를 이용해 구현한다.

 

🤔  BFS를 응용해 풀 수 있는 문제

- 가중치가 있는 그래프의 최단거리 (다익스트라 알고리즘과 같이 최단 경로 탐색 시 많이 활용)

🤔  BFS vs DFS
(어떤 상태에서의 답을 구하기 위해 어떤 경로를 따라 끝까지 들어가봐야 하는 경우에는 BFS로는 잘 안 된다.
마지막까지 일단 들어갔다가, 돌아오는 길에 거쳐갔던 정점(vertex)들에 대한 답을 순차적으로 갱신해줘야 하는 경우가 있다.
그리고 BFS로 풀 수 있다고 하더라도, DFS가 훨씬 직관적이고 구현하기 편한 경우들도 무수히 존재한다.)

 

 

🤔  BFS의 핵심 이론

BFS는 한 번 방문한 노드를 다시 방문하면 안된다.
따라서 노드 방문여부를 체크할 리스트가 필요하다.

BFS 탐색방식은 FIFO특성의 큐를 사용해 설명하자면, 아래와 같다.

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화 
- BFS를 위해 필요한 초기 작업 아래와 같다.
  ‣ 인접리스트로 그래프를 표현
  ‣ 방문리스트를 초기화하기
  ‣ 시작 노드 스택에 삽입하기
- 큐에 시작노드를 1로 삽입할 때, 해당 위치의 방문리스트를 체크하면 T, F, F, F, F, F 이다.

 
2. 큐에서 노드를 꺼내 인접 노드를 다시 큐에 삽입 
- 큐에서 노드를 꺼내면서 인접노드를 큐에 삽입한다.
- 이때, 방문 리스트를 체크하여 이미 방문한 노드는 큐에 삽입하지 않으며 꺼낸 노드는 탐색순서에 기록한다.
- 이때, 방문리스트는 T, T, T, F, F, F 이고 탐색 순서는 1이다.

1을 꺼낼 때 탐색순서에 1을 기록하고 인접노드 3, 2를 큐에 삽입하며 방문리스트에 체크한다.

 

3. 큐에 값이 없을 때까지 반복 
- 앞선 과정을 큐 자료구조에 값이 없을 때까지 반복하며 이미 거친 노드는 재삽입 하지 않는 것이 핵심!
- FIFO 방식으로 탐색하기에 탐색 순서가 DFS와 다름을 유의해야 한다!
- 이때, 최종적인 탐색순서는 1 - 2 - 3 - 5 - 6 - 4 이다.

2, 3 순서로 노드를 꺼내며 인접 노드를 큐에 삽입한다.
2의 경우 5, 6은 아직 방문하지 않았기에 방문리스트를 체크하며 모두 삽입한다.
3의 경우 4 역시 방문한 적이 없어서 방문리스트를 체크하며 삽입한다.
이때, 탐색순서는 2, 3이 기록된다.

5와 6을 꺼낼 때, 인접노드가 없기에 탐색순서에 기록만 하고 꺼낸다.
4를 꺼낼 때 인접노드는 6이지만 이미 앞서 방문했기에 6은 삽입하지않고 꺼내기만 한다.

 

 

 

🤔 BFS 수도코드

BFS의  구현

BFS를 구현하는 경우의 수도 코드는 다음과 같다.

BFS(너비 우선 탐색)는 시작 정점(vertex)으로부터 거리가 가까운 정점들을 먼저 차례로 방문하고
멀리 떨어져 있는 정점을 나중에 방문하는 운행 방법이다. (점차 영역을 넓혀나간다고 생각하면 쉽다.)
BFS는 DFS보다 쓰임새는 적지만, 다익스트라 알고리즘과 같이 최단 경로 탐색 시 많이 활용된다.
BFS는 재귀로 구현되지 않고 오직 큐를 이용한 반복 구조를 통해 구현된다는 점을 명심하자. 

<pseudocode>

BFS(G, start_v)
    let Q be a queue
    mark start_v as visited
    Q.enqueue(start_v)
    while Q is not empty do
        v := Q.dequeue()
        if v is the goal then
            return v
        for all edges from v to w in G.adjacentEdges(v) do
            if w is not marked as visited then
                label w as visited
                w.parent := v
                Q.euqueue(w)

 

수도코드를 살펴보면 하나의 정점에 대한 인접 간선을 모두 추출하고 도착점인 정점을 큐에 삽입하는 방식으로 동작한다.
코드의 전개는 앞의 DFS 스택 구현과 크게 다르지 않다.
다만, 여기서는 FIFO 구조의 큐를 활용했기 때문에 너비 우선 탐색, 즉 가까운 정점부터 모두 탐색해두고 그 다음 거리의 정점으로 탐색 범위를 넓혀나가는 운행 방식이 가능해지는 것이다.

<python code>

def bfs(start_v):
    visited = [start_v]
    Q = deque([start_v])
    while Q:
        v = Q.popleft()
        for w in graph[v]:
            if w not in visited:
                visited.append(w)
                Q.append(w)

    return visited

 

 

 

 

 

효율성

- 앞서 언급했던 DFS와 다르지 않다.

• 시간 복잡도

인접 행렬의 경우 하나의 정점 당 n번 check를 해주어야 하기 때문에 O(n^2)이다.
인접 리스트의 경우 정점 방문 & 해당 정점의 인접 정점 방문이므로 O(n+m)이다.
시간 복잡도의 경우에는 결국엔 어떤 정점을 탐색하느냐의 문제이기 때문에 공간 복잡도와 동일하다.

 

• 공간 복잡도

공간 복잡도의 경우, 그래프와 visited, 스택을 모두 고려해주어야 하기에 그래프의 공간복잡도는 다음과 같다.
인접 행렬의 경우에는 하나의 정점과 모든 정점 간의 연결 관계를 다 표현해주어야 하기 때문에 O(n^2)이다.
인접 리스트의 경우에는 그래프 내 정점 개수를 n, 간선 개수를 m이라고 할 때 O(n+m)이다.

결과적으로 공간복잡도는 그래프의 공간복잡도를 따라 가게 된다.

BFS의 효율성에 대해 말할 경우, 스택과 visited는 모두 O(n)의 공간복잡도를 가지고 있다 (정점 개수 n).
이는 그래프가 인접 행렬이나 인접 리스트로 구현되어 있든 두 가지 경우 모두에 해당한다.

 

 

 

 

🧐 백준 1260 (DFS와  BFS)

🤔 Algorithm 과정_ DFS 
1. 그래프를 인접리스트로 저장한다. (무방향 그래프이기에 양쪽방향으로 간선을 모두 저장한다.)
2. 방문리스트를 모두 False로 초기화한다.
3. 재귀를 이용한 DFS를 수행하는데, 아래와 같이 진행한다.

🤔 Algorithm 과정_ BFS 
1. 그래프를 인접리스트로 저장한다. (무방향 그래프이기에 양쪽방향으로 간선을 모두 저장한다.)
2. 방문리스트를 모두 False로 초기화한다. (이때, 위의 DFS에서 사용했기에 초기화를 반드시 해줘야 한다!)
3. BFS를 수행하는데, 아래와 같이 진행한다.

이를 풀이하면 다음과 같다.

1. 큐 자료구조에 starting_vertex 삽입
visit_list에 현재 vertex 기록

2. while (큐가 빌 때 까지):
	큐에서 vertex를 가져와 출력
    현재 vertex의 연결vertex 중 미방문 vertex를 큐에 삽입(append)
    방문리스트에 기록

🤫  solution_1260

import sys
input = sys.stdin.readline

V, E, starting_vertex = map(int, input().split())

# graph라는 인접리스트 생성
#         [1]      [2]     [3]       [4]
# [[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3], []]
graph = [[] for _ in range(V+1)]
for _ in range(E):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

# 정점에 우선순위가 부여되었으므로 정렬
for i in range(V+1):
    graph[i].sort()

# 방문리스트 생성
visit_list = [False] * (V+1)

def DFS(v):
    print(v, end = " ")
    visit_list[v] = True
    for i in graph[v]:
        if not visit_list[i]:
            DFS(i)

from collections import deque
def BFS(v):
    queue = deque()
    queue.append(v)
    visit_list[v] = True
    while queue:
        curr_vertex = queue.popleft()
        print(curr_vertex, end = " ")
        for i in graph[curr_vertex]:
            if not visit_list[i]:
                visit_list[i] = True
                queue.append(i)


# DFS 출력
DFS(starting_vertex)
print()

visit_list = [False] * (V+1)    # 리스트 초기화
# BFS 출력
BFS(starting_vertex)