on
탐색 알고리즘 DFS/BFS
탐색 알고리즘 DFS/BFS
DFS
DFS는 Depth-First search의 약자이다. 직역하자면 깊이 우선탐색이며, 그래프의 가장 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
먼저 그래프(Graph)의 기본 구조를 알 필요가 있다.
그래프는 노드(Node)와 간선(Edge)로 표현되며 (노드를 정점(Vertex)라고도 한다)
(A라는 도시[노드] 에서 B라는 도시[노드]로 이동하기 위한 도로[간선]을 거친다고 이해하면 된다.)
프로그래밍에서 그래프는 2가지 방식으로 표현되는데 두개념에 대해 정확히 아는것이 좋다.
- 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식
- 인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식
아래와 같은 노드와 간선을 가진 그래프가 있다고 하자.
인접 행렬 방식
인접 행렬 방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. 각 노드가 연결된 형태를 기록하는 방식이다. 위 그래프를 인접 행렬로 표현하려면 파이썬에서 2차원 리스트를 구현해야 한다. 그리고 그래프에서 연결되지 않은 노트는 무한의 비용이라고 선언한다. (실제 코드에서 답이 될수없는 말도안되는 큰수 1e9, 9999999 등으로 표현)
그래프 인접 행렬 방식은 다음과 같이 코드로 구현할 수 있다.
인접 행렬 방식
INF = 1e9 # 무한의 비용 선언
# 2차원 리스트를 이용해 인접 행렬 표현
graph =[
[ 0 , 7 , 5 ],
[ 7 , 0 , INF ],
[ 5 , INF , 0 ]
]
print ( graph )
>>[[ 0 , 7 , 5 ], [ 7 , 0 , 1000000000.0 ], [ 5 , 1000000000.0 , 0 ]]
graph안의 0번째 리스트[0번째 노드]안의 1번째[1번 노드], 2번째[2번 노드] 원소 값은 7[간선], 5[간선]이다.
인접 리스트 방식
인접 리스트 방식은 아래 그림처럼 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다.
인접 리스트는 '연결 리스트' 라는 자료구조를 이용해 구현한다. C++, 자바같은 프로그래밍 언어는 별도의 연결리스트를 표준 라이브러리로 제공하나, 파이썬은 기본자료형인 리스트가 append( ) 메소드를 제공하므로 배열,연결 리스트의 기능을 기본으로 제공한다. 인접리스트 또한 2차원 리스트를 이용해야 한다는 것을 기억하자.
인접 리스트 방식
# 행(Row)이 3개(노드의 갯수)인 2차원 리스트로 인접리스트 표현
graph =[[] for _ in range ( 3 )]
# 노드 0에 연결된 노드 정보 입력(노드,거리)
graph [ 0 ]. append (( 1 , 7 ))
graph [ 0 ]. append (( 2 , 5 ))
# 노드 1에 연결된 노드 정보 입력
graph [ 1 ]. append (( 0 , 7 ))
# 노드 2에 연결된 노드 정보 입력
graph [ 2 ]. append (( 0 , 5 ))
print ( graph )
>>[[( 1 , 7 ), ( 2 , 5 )], [( 0 , 7 )], [( 0 , 5 )]]
0번째 리스트[0번째 노드] 안의 튜플의 첫번째 원소는 연결된 노드 이며 두번째 원소는 해당 노드와의 거리이다.
인접행렬, 인접리스트 두가지 방식의 차이
메모리적인 측면에서 살펴보면 인접 행렬 방식은 모든 관계(연결되지 않은 노드라도 관계를 저장) 하므로 노드의 개수가 많을 수록 불필요한 메모리가 낭비된다. 반면 인접 리스트 방식은 연결된 정보반 저장 하므로 메모리 사용이 효율적이다.
하지만 그런 속성 때문에 인접 리스트 방식은 인접 행렬방식에 비해 두 노드간의 연결 정보를 얻는 속도가 느리다. 인접 리스트 방식은 해당 노드에 연결된 데이터를 전부 꺼내서 확인해야 하기 때문이다.
예를 들어 노드 1과 7이 연결되어 있을 때 인접 행렬은 graph[1][7]을 확인하면 연결정보를 알 수 있다. 하지만 인접 리스트 방식은 graph[1]을 호출하여 for i in graph[1] 을 사용해 인접 리스트를 앞에서부터 확인 해야 한다.
하지만 반대로 특정한 노드와 연결된 모든 인접 노드를 순회 해야 하는 경우, 인접 리스트 방식이 인접 행렬 방식 에 비해 메모리 공간 낭비가 적다.
DFS의 구체적 동작 과정
DFS는 깊이 우선 탐색 알고리즘 이라고 하였다. 이 알고리즘은 특정한 경로를 탐색하다 특정한 상황이 되면 최대한 깊숙이 들어가서 노드를 방문 후, 다시 돌아가 다른 경로를 탐색 하는 알고리즘이다.
1. 탐색 시작 노드를 스택에 삽입 후 방문처리를 한다.
(방문 처리란 한번 삽입 되어 처리된 노드가 다시 삽입 되지 않게 하며, 각 노드를 한번씩만 처리하게 한다)
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리를 한다.
방문 하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼낸다.
3. 2번 과정을 더이상 수행할 수 없을 때 까지 반복한다.
아래와 같은 그래프가 있다고 하자, 1번 노드를 시작 노드로 설정하고 DFS를 이용해 탐색 해보자.
step1. 시작 노드 1을 스택에 삽입하고 방문처리한다.
방문 처리 1 2 3 4 5 6 7 8 스택 1
step2. 스택 최상단 노드인 '1'에 방문하지 않은 인접 노드 2, 3, 8이 있다. 가장 작은 2를 스택에 넣고 방문처리한다.
step3. 스택 최상단 노드인 '2'에 방문하지 않은 인접 노드 '7'이 있다. '7'번 노드를 스택에 넣고 방문 처리한다.
step4. 스택 최상단 노드인 '7'에 방문하지 않은 인접 노드 6, 8이 있다. 이중 가장 작은 6을 스택에 넣고 방문처리한다.
방문 처리 1 2 3 4 5 6 7 8 스택 1 2 7 6
step5. 스택의 최상단노드인 '6'은 방문하지 않은 인접노드가 없다. 따라서 '6번' 노드를 꺼낸다.
방문 처리 1 2 3 4 5 6 7 8 스택 1 2 7
step6. 스탭 최상단 노드인 '7'에 방문하지 않은 인접 노드 8이 있다. 8을 스택에 넣고 방문처리 한다.
방문 처리 1 2 3 4 5 6 7 8 스택 1 2 7 8
step7. 스탭 최상단 노드인 '8'에는 방문하지 않은 인접 노드가 없다. 따라서 노드 8을 스택에서 꺼낸다.
step8. 마찬가지로 인접 노드가 없는 7번 그리고 2번 노드를 차례로 꺼낸다.
방문 처리 1 2 3 4 5 6 7 8 스택 1
step9. 스택 최상단 노드 '1'의 방문하지 않은 인접노드 3을 스택에 넣고 방문처리한다.
step10. 스택 최상단 노드 '3'의 방문하지 않은 인접노드 4, 5중 가장 작은 4를 스택에 넣고 방문처리한다.
step11. 스택의 최상단 노드 '4'의 방문하지 않은 인접노드 5를 스택에 넣고 방문처리한다.
방문 처리 1 2 3 4 5 6 7 8 스택 1 3 4 5
step12. 이제 stack안에 방문 하지않은 인접노드가 없다. 차례대로 노드를 5>4>3>1의 순서로 노드를 꺼내준다.
방문 처리 1 2 3 4 5 6 7 8 스택
결과적으로 노드의 탐색순서(스택에 들어간 순서) 는
1 > 2 > 7 > 6 > 8 > 3 > 4 > 5
이다. DFS는 스택 자료구조에 기초 하므로 구현이 간단하다. 실제로는 스택을 사용하지 않아도 되며, 데이터가 N개일 경우 O(N) 의 시간 복잡도를 가진다. 또한 DFS는 스택을 이용하므로 실제 구현에서 재귀함수를 이용하면 간결하게 표현이 가능하다.
DFS 소스코드
def dfs ( graph , v , visited ):
visited [ v ]= True # 탐색한 노드는 방문처리
print ( v , end = ' ' ) # 탐색순서대로 출력
for i in graph [ v ]: # 인접한 노드 중
if not visited [ i ]: # 방문하지 노드
dfs ( graph , i , visited ) # 재귀적으로 방문(=스택)
v , e = map ( int , input (). split ()) # 노드와 간선의 갯수 입력받기
graph =[[] for _ in range ( v + 1 )] # 그래프의 정보 입력받기
for _ in range ( e ):
a , b = map ( int , input (). split ()) # a는 b와 연결
graph [ a ]. append ( b )
graph [ b ]. append ( a )
# 방문여부 확인을 위한 리스트
visitied =[ False ]*( v + 1 )
# DFS함수 호출
dfs ( graph , 1 , visitied )
>> 1 2 7 6 8 3 4 5
BFS
BFS(Breadth First Search) 알고리즘은 '너비 우선 탐색' 이라는 의미를 가진다. 쉽게 말해 가까운 노드 부터 탐색하는 알고리즘이다. DFS는 최대한 멀리 있는 노드를 우선 탐색 하지만, BFS는 그 반대이다. BFS 구현에선 선입선출 방식인 큐 자료구조를 이용한다. 인접한 노드를 반복적으로 큐에 넣으면 자연스럽게 먼저 들어온것이 먼저 나가며, 이는 가까운 노드를 탐색하는 것과 동일하기 때문이다. 동작 방식은 다음과 같다.
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2의 과정을 더이상 수행할 수 없을 때 까지 반복한다.
마찬가지로 DFS에서 예로 든 그래프로 과정을 살펴보자.
step1. 시작 노드 1을 큐에 삽입 후, 방문처리를 한다.
방문 처리 1 2 3 4 5 6 7 8 큐 1
step2. 큐에서 노드 1을 꺼내고, 방문 하지않은 인접노드 2, 3, 8을 모두 큐에 삽입 후 방문처리를 한다.
방문 처리 1 2 3 4 5 6 7 8 큐 2 3 8
step3. 큐에서 노드 2를 꺼내고 방문하지 않은 인접노드 7을 큐에 삽입 후 방문처리한다.
노드 3을 꺼내고 방문하지 않은 인접노드 4, 5를 큐에 삽입 후 방문 처리한다.
방문 처리 1 2 3 4 5 6 7 8 큐 8 7 4 5
step4. 큐에서 노드 8을 꺼내고 방문하지 않은 인접 노드가 없으므로 pass한다.
step5. 큐에서 노드 7을 꺼내고 방문하지 않은 인접 노드 6을 큐에 삽입 후 방문 처리한다.
방문 처리 1 2 3 4 5 6 7 8 큐 4 5 6
step6. 이제 방문하지 않은 인접 노드가 없으므로 노드를 4>5>6의 순서로 꺼낸다.
방문 처리 1 2 3 4 5 6 7 8 큐
결과적으로 노드의 탐색 순서 (큐에 들어간 순서)는
1 > 2 > 3 > 8 > 7 > 4 > 5 > 6
이다. BFS는 큐 자료구조에 기초하여 구현하며 실제 구현에서는 deque 라이브러리를 사용하는것이 더 편하다. 시간 복잡도는 DFS와 마찬가지로 O(N) 이다. (빅오 표기법으로는 같지만 일반적으로 DFS보다 수행시간이 좋다.)
BFS 소스코드
from collections import deque
def bfs ( graph , start , visitied ):
q = deque ([ start ]) # 큐에 시작 노드를 넣은 채로 시작
visitied [ start ]= True # 시작 노드 방문처리
while q : # q가 빌때 까지 반복
v = q . popleft () # 큐안의 노드를 꺼낸다.
print ( v , end = ' ' ) # 탐색 순서대로 출력
for i in graph [ v ]: # 해당 노드와 인접한 노드 중
if not visitied [ i ]: # 방문하지 않은 노드라면
q . append ( i ) # 큐에 넣은 후
visitied [ i ]= True # 방문 처리한다.
v , e = map ( int , input (). split ()) # 노드,간선의 개수 입력받기
graph =[[] for _ in range ( v + 1 )] # 그래프의 정보 입력받기
for _ in range ( e ):
a , b = map ( int , input (). split ()) # a는 b와 연결
graph [ a ]. append ( b )
graph [ b ]. append ( a )
# 방문여부 확인을 위한 리스트
visitied =[ False ]*( v + 1 )
# BFS함수 호출
bfs ( graph , 1 , visitied )
>> 1 2 3 8 7 4 5 6
DFS와 BFS의 구현에 대해 알아 보았고 마지막으로 간결하게 정리하자면 다음 과 같다.
DFS BFS 동작 원리 스택 큐 구현 방법 재귀 함수 이용 큐 자료구조(deque)이용
from http://20210916start.tistory.com/88 by ccl(A) rewrite - 2021-09-28 09:01:04