DFS / BFS 알고리즘과 예제풀이 ( 백준 바이러스, BFS 와 BFS 파이썬 )

출처 : Quora

대표적인 그래프탐색 알고리즘 DFS, BFS 핵심 요약 및 백준 기본문제풀이.

*하기 글에서 노드(node), 정점(vertex)를 혼용해서 사용하는데 동일한 것을 의미함

BFS (Breadth First Search, 너비 우선 탐색)

Introduction to algoritm 번역본 중

주어진 그래프 G(V, E)에서 출발절 s에 대해 너비우선검색은 도달가능한 모든 정점을 체계적으로 탐색함.

s(시작점)에서 도달할 수 있는 모든 v(정점)에 대해, 너비우선트리의 단순경로는 그래프 G의  s에서 v까지의 최단경로에 해당하고, 이는 가장 적은 개수의 간선을 가지는 경로다. 너비 우선 검색은 발견된 정점과 발견되지 않은 정점 사이에 있는 경계선(frontier)을 균등하게 확장해 나간다는 의미로 이름이 붙었다. 즉, 이 알고리즘은 s로부터 거리가 k+1인 항 정점을 만나기 전에 s로부터 거리가 k인 점을 모두 발견하는 알고리즘이다.

 

번역본이라 조금 어렵지만 개인적으로 핵심이라고 생각하는 두 문장만 highlight로 표시했다. 

너비우선탐색에서 말하는 최단거리는 노드 데이터 누적값의 최솟값을 의미하는 것이 아니라, 시작점 기준으로 가장 적은 간선의 개수를 갖는 경로를 의미한다. 다시말해, 시작 노드 기준으로 간선 n개 떨어진 노드에 닿기 전에 1~n-1 만큼 떨어진 노드까지 다 탐색이 되어있다는 뜻이다. 다시 위 이미지 좌측부분을 보면 쉽게 이해할 수 있다. 그래프가 트리형태가 아니더라도 특성은 동일하게 유지된다. 

• 구현 - 큐 + While을 이용해 구현한다. 파이썬을 통한 구현은 하기 예제를 참고.

##기본 예제 백준 2602 바이러스 BFS 풀이 

import sys
N_computer=int(input())
visited=[False]*(N_computer+1)
N_E=int(input())
E=[[] for i in range(N_computer+1)]

for i in range(N_E):
    S,D = map(int, input().split())
    E[S].append(D)
    E[D].append(S)
count=0

##bfs풀이
from collections import deque
def bfs(E,v,visited):
    queue=deque([v])  #시작점을 큐에 넣는다.
    visited[v]=True   #시작점 방문처리
    global count
    while queue: 
        x=queue.popleft()      #큐에서 가장 앞에 있는 노드와 인접한 노드 탐색
        for i in E[x]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True 
                count+=1
bfs(E,1,visited)
print(count)

DFS (Depth First Search, 깊이 우선 탐색) 

 

Introduction to algoritm 번역본 중

가능한 한 그래프에서 "더 깊이" 검색하는 것이다. 깊이 우선 탐색은 가장 최근에 발견되고 아직 조사하지 않은 간선을 가진 정점 v로부터 나오는 간선을 조사한다. v의 모든 간선이 조사되면 그 검색은 v를 발견하게 해준 정점으로부터 나오는 간선을 조사하기 위해 "뒤로 돌아간다" 이 과정은 원래의 출발점으로부터 도달할 수 잇는 모든 정점이 발견될 때까지 계속된다. 발견되지 않은 정점이 하나라도 남아있으면 깊이 우선검색은 그 중 하나를 새 출발점으로 선택하고 해당출발점으로부터의 검색을 반복한다. 전체 과정을 모든 정점을 발견할 때까지 반복한다.

 

현재의 노드(정점) 기준으로 연결되어있는 모든 정점을 순차적으로 방문하는 BFS와는 달리, DFS의 경우 가장 최근의 발견된 노드와 그 노드의 가장 최근의 발견된 노드, 그리고 그노드의 가장 최근에 발견한 노드를 계속 반복탐색한다. 종료 조건을 만나거나(백 트래킹), 가장 하단 노드인 leaf 까지 도달하면, 탐색되지 않은 노드를 새 출발점으로 삼아 재탐색을 시작한다.

• 구현 - 재귀 함수를 통한 구현, 혹은 스택을 이용하여 구현하는 방법이 있다. 하기 예제를 참고.

1. 스택 + While문을 이용한 DFS 구현풀이

## DFS Stack + 반복문을 이용한 풀이

import sys
N_computer=int(input())
visited=[False]*(N_computer+1)
N_E=int(input())
E=[[] for i in range(N_computer+1)]

for i in range(N_E):
    S,D = map(int, input().split())
    E[S].append(D)
    E[D].append(S)
count=0

# #dfs풀이 (스택 이용)
from collections import deque
def dfs(E,v,visited):
    global count
    stack=deque()
    stack.append(v)  #시작노드 스택에 넣기
    while stack:
        x=stack.pop()   #가장 최근에 삽입된 노드 pop후 인접노드 Stack
        visited[v]=True
        for i in E[x]:
            if not visited[i]:
                stack.append(i)
                visited[i]=True
                count+=1

dfs(E,1,visited)
print(count)

2. 재귀함수를 이용한 DFS 구현풀이

##기본 예제 백준 2602 바이러스 DFS 풀이 // 재귀함수를 이용한 DFS

import sys
N_computer=int(input())
visited=[False]*(N_computer+1)
N_E=int(input())
E=[[] for i in range(N_computer+1)]

for i in range(N_E):
    S,D = map(int, input().split())
    E[S].append(D)
    E[D].append(S)
count=0

##dfs풀이
def dfs(E, v, visited):
    visited[v]=True    #시작노드 방문처리
    global count
    for i in E[v]:         #시작노드와 인접한노드 순차적 탐색
        if not visited[i]:
            count+=1
            dfs(E, i, visited)
dfs(E, 1, visited)
print(count)

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

2606번: 바이러스

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

1260번: DFS와 BFS