이번 글에서는 코딩테스트 출제 빈도가 아주 높은 알고리즘은
BFS 너비우선탐색과 DFS 깊이우선탐색 에 대해 소개하겠습니다.
이번 정리 역시 프로그래머스에서 코딩테스트 연습을 하다가 BFS/DFS 영역의 문제를 풀기전 개념을 다시 한 번 정확히 정리해보고자 정리한 글입니다.
BFS와 DFS는 그래프 자료구조를 탐색할 때 사용되는 기법입니다. 두 기법 모두 그래프에 속한 모든 노드를 방문하는 것을 목적으로 하는데, 탐색 우선 순위를 어떤 것으로 두는 지에 따라 두 기법의 차이가 있습니다.
너비 우선 탐색 BFS (Breath First Search)
-
BFS의 개념
BFS는 이름에서 알 수 있듯이, 너비 Breath를 우선으로 탐색하는 기법입니다. 그래프 탐색의 시작점 (루트 또는 특정 노드) 과 같은 거리에 있는 노드를 우선적으로 방문하는 것입니다.그래서 BFS는 매 단계에서 가능한 모든 경우의 수를 확인할 수 있습니다.
-
Queue 큐
BFS 알고리즘 구현의 핵심을 큐 (Queue) 자료구조를 활용하여
현재 방문한 노드의 인접한 노드 중 방문하지 않은 노드를 큐에 넣어 두고, 큐에 들어있는 노드부터 방문하면 됩니다.
파이썬에서는 list 자료형을 큐로 사용할 수 있습니다.
-
Example
너비우선탐색으로 그래프의 노드를 방문하는 과정은 위와 같습니다.
방문한 노드는 검정색으로 칠하고, 방문을 한 노도에 인접한 노드는 큐에 삽입한 뒤 회색으로 칠합니다. 그리고 아예 큐에도 삽입되지 않은 노드는 흰색으로 남겨둡니다.
위 과정을 설명해보자면 a에 방문하여 검정색으로 칠하고, 인접한 노드인 b와 c를 큐에 삽입하고 회색으로 칠합니다.
| HEAD | b, c | TAIL |
그 다음 방문할 노드는 큐에서 찾습니다. 큐의 head에서 방문할 노드를 선택하여 b를 방문하게 됩니다.
b에 방문했으니 b는 큐에서 pop되고, 검정색으로 칠합니다. 그리고 b의 인접 노드인 d와 e를 큐에 삽입하고 회색으로 칠합니다.
| HEAD | c, d, e | TAIL |
그리고 난 뒤 또 큐의 head에서 c를 방문하고, b를 방문했을 때와 같은 방식으로 큐에서 pop하고 검정색을 칠한 뒤,
c의 인접 노드인 f와 g를 큐에 삽입하고 회색으로 칠합니다. 그럼 큐는 아래와 같은 상태를 가지게 됩니다.
| HEAD | d,e,f,g | TAIL |
이런 방식으로 노드를 차례대로 방문하고, 큐가 비게 되면 모든 노드를 방문한 것이므로 탐색을 종료하게 됩니다.
최종적으로 BFS로 노드 탐색 순서는 아래와 같습니다.
| a-b-c-d-e-f-g-h |
-
Implementation (Python3)
위 그래프는 딕셔너리와 리스트 자료형을 이용해 코드로 표현했습니다.
딕셔너리의 키는 해당 노드를 나타내고, 밸류는 키에 인접한 노드를 저장한 리스트를 갖습니다.
gragh = {
'a' : ['b','c'],
'b' : ['a','d','e'],
'c' : ['a','f','g'],
'd' : ['b'],
'e' : ['b','h'],
'f' : ['e'],
'g': ['g'],
'h': ['e']
}그리고 BFS는 다음과 같이 구현합니다. 설명은 주석을 참고해주세요 :)
def bfs(graph, start_node):
visit = list()
# current_node의 인접한 노드를 담을 큐
queue = list()
queue.append(start_node)
# queue가 비게되면 반복문 종료
while queue:
# 큐의 head에 있는 값을 pop해서 current_node에 저장
current_node = queue.pop(0)
# current_node가 아직 방문하지 않은 노드라면
if current_node not in visit:
# visit에 current_node 추가
visit.append(current_node)
# current_node를 키로 하는 밸류 리스트 = graph(current_node)를 queue에 extend
# 즉, current_node의 인접한 노드들을 queue에 삽입
queue.extend(graph[current_node])
# current_node가 이미 방문한 노드라서 visit에 있는 경우 if 문을 그냥 지나침
# queue가 빈 상태가 되어 while 문이 끝나면 visit을 반환
return visit ** 참조 블로그에서는 일반적인 리스트로 pop(0)으로 큐를 사용하여 효율이 떨어지기 떄문에 큐 모듈을 사용하여 popleft()하는 것이 좋다고 합니다!
위 코드를 실행하면 결과는 다음과 같이 나옵니다.
def bfs(graph, start_node):
visit = list()
# current_node의 인접한 노드를 담을 큐
queue = list()
queue.append(start_node)
# queue가 비게되면 반복문 종료
while queue:
# 큐의 head에 있는 값을 pop해서 current_node에 저장
current_node = queue.pop(0)
# current_node가 아직 방문하지 않은 노드라면
if current_node not in visit:
# visit에 current_node 추가
visit.append(current_node)
# current_node를 키로 하는 밸류 리스트 = graph(current_node)를 queue에 extend
# 즉, current_node의 인접한 노드들을 queue에 삽입
queue.extend(graph[current_node])
# current_node가 이미 방문한 노드라서 visit에 있는 경우 if 문을 그냥 지나침
# queue가 빈 상태가 되어 while 문이 끝나면 visit을 반환
return visit
if __name__ == "__main__":
gragh = {
'a' : ['b','c'],
'b' : ['a','d','e'],
'c' : ['a','f','g'],
'd' : ['b'],
'e' : ['b','h'],
'f' : ['e'],
'g': ['g'],
'h': ['e']
}
print(bfs(gragh, 'a'))
깊이 우선 탐색 DFS (Depth First Search)
-
DFS의 개념
DFS는 '깊이'를 우선적으로 탐색하는 기법으로 한 방향으로 갈 수 있는 깊게 탐색하는 것입니다.
즉, 시작 노드에서 한 방향으로 나아갈 수 있는 한 노드를 방문하고 리프 노드에 도달할 때까지 한 방향으로 탐색을 합니다.
-
Stack 스택
DFS는 BFS와 코드가 유사한데 큐를 사용한 BFS와 달리 스택(Stack)을 사용합니다. 시작 노드를 스택에 삽입하고, pop하면서 방문했음을 표시합니다. 그리고 현재 방문한 노드의 자식 노드들을 스택에 삽입합니다. 그리고 스택 top 에 있는 노드를 pop하고 방문했음을 표시하고, 해당 노드의 자식 노드를 또 다시 스택에 삽입합니다.이 과정을 반복하면서 마침내 스택이 비게 되면 모든 노드를 방문한 것입니다.
-
Example
깊이우선탐색이 노드를 방문하는 방식은 위와 같습니다.
탐색 시작 노드 1 을 스택이 삽입하고, 방문 했음을 표시하면서 pop 합니다. 그리고 1의 자식 노드들을 스택에 삽입하면 스택의 상태는 다음과 같이 됩니다.
| TOP |
| 2 |
| 5 |
| 9 |
| BOTTOM |
그 다음은 스택 탑인 2를 방문하고, 방문했음을 표시하고 pop 합니다. 그리고 2의 자식 노드인 3을 스택에 삽입합니다.
| TOP |
| 3 |
| 5 |
| 9 |
| BOTTOM |
그리고 다시 반복하여 스택 탑에 있는 3을 방문하고, 방문했음을 표시하고, pop 한뒤, 3의 자식 노드인 4를 스택에 삽입합니다.
| TOP |
| 4 |
| 5 |
| 9 |
| BOTTOM |
스택 탑에 있는 4를 방문하고, 방문했음을 표시하고, pop 합니다. 4는 자식 노드가 없으므로 스택에 삽입할 노드가 없습니다.
| TOP |
| 5 |
| 9 |
| BOTTOM |
이렇게 되면 한 방향의 리프노드까지 도달했으므로 한 방향의 탐색은 끝이 난 것입니다. 그리고 처음 분기점이었던2, 5, 9 노드로 돌아가 그 중 아직 방문 표시가 되지 않은 5와 9부터 다시 깊이탐색을 시작하는 것입니다. 간단히 스택의 탑부터 다시 그동안의 과정을 반복해주면 되는 것이죠!
-
Implementation (Python3)
그래프 자료 구조는 BFS와 동일하게 표현했습니다.
DFS 함수는 다음과 같이 구현했습니다. 설명은 주석을 참고해주세요 :)
def dfs(graph, start_node):
visit = list()
stack = list()
stack.append(start_node)
# stack이 비게되면 반복문 종료
while stack:
# 스택 탑에 있는 값을 pop해서 current_node에 저장
current_node = stack.pop()
# current_node가 아직 방문하지 않은 노드라면
if current_node not in visit:
# visit에 current_node 추가해서 방문했음을 표시
visit.append(current_node)
# current_node를 키로 하는 밸류 리스트 = graph(current_node)를 queue에 extend
# 즉, current_node의 자식 노드를 스탭에 삽입
stack.extend(graph[current_node])
# current_node가 이미 방문한 노드라서 visit에 있는 경우 if 문을 그냥 지나침
# 스택이 빈 상태가 되어 while 문이 끝나면 visit을 반환
return visit DFS를 실행한 결과 탐색 순서는 다음과 같습니다.
def dfs(graph, start_node):
visit = list()
stack = list()
stack.append(start_node)
# stack이 비게되면 반복문 종료
while stack:
# 스택 탑에 있는 값을 pop해서 current_node에 저장
current_node = stack.pop()
# current_node가 아직 방문하지 않은 노드라면
if current_node not in visit:
# visit에 current_node 추가해서 방문했음을 표시
visit.append(current_node)
# current_node를 키로 하는 밸류 리스트 = graph(current_node)를 queue에 extend
# 즉, current_node의 자식 노드를 스탭에 삽입
stack.extend(graph[current_node])
# current_node가 이미 방문한 노드라서 visit에 있는 경우 if 문을 그냥 지나침
# 스택이 빈 상태가 되어 while 문이 끝나면 visit을 반환
return visit
if __name__ == "__main__":
gragh = {
'a' : ['b','c'],
'b' : ['a','d','e'],
'c' : ['a','f','g'],
'd' : ['b'],
'e' : ['b','h'],
'f' : ['e'],
'g': ['g'],
'h': ['e']
}
print(dfs(gragh, 'a'))
이번 글에서는 BFS와 DFS의 개념에 대해 알아보고 간단히 구현해보았습니다.
코딩테스트나 기술 면접에 아주 자주 출제되는 개념이라고 하니 잘 알아두어야겠습니다 ㅎㅎ
글을 작성하고 조금 더 구글링을 해보니 제가 작성한 코드를 조금 효율이 떨어지는 것 같습니다.
** deque를 사용하거나 그래프 구현시 딕셔너리가 아니라 리스트로 구현해서
set 함수를 활용하는 방식 등이 있다고 하네요
더 효율적인 코드로 발전해보겠습니다 ㅎㅎ
감사합니다 :)
References
'컴퓨터 공학 > 알고리즘' 카테고리의 다른 글
| 분할정복 Divide & Conquer 알고리즘, 합병정렬 Merge Sort 이해하기 (0) | 2021.02.10 |
|---|---|
| Big-O notation (0) | 2021.02.09 |
| 완전 탐색 Exhaustive Search (0) | 2021.01.21 |
| 정렬 알고리즘 (3) : 합병 정렬, 퀵 정렬 (0) | 2021.01.14 |
| 정렬 알고리즘 (2) : 삽입 정렬, 버블 정렬 (0) | 2021.01.13 |
