[자료구조] DFS(깊이 우선 탐색) & BFS(너비 우선 탐색) (in python)

💡 그래프 탐색

• 하나의 노드에서 시작하여 노드와 연결된 모든 정점들을 한 번씩 방문하는 것

💡 DFS (깊이 우선 탐색)

DFS는 이름 그대로 깊이를 우선으로 탐색하는 방법이다. 전회 순회라고도 할 수 있는데 쉽게 말하면 아래 그림처럼, "루트 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리" 순으로 방문하는 방식이다.

그리고 이 과정이 재귀적으로 반복된다고 이해하면 된다. 왼쪽 서브트리에 방문하면 왼쪽 서브트리에서는 왼쪽 서브트리의 루트 노드를 먼저 방문하고 그 루트 노드의 왼쪽 서브트리 -> 오른쪽 서브트리를 방문하는 방식이다.

출처 : https://velog.io/@tomist0930/dfs

예시를 통해 더욱 쉽게 이해할 수 있는데, 만약 그래프가 위와 같다고 하면 DFS의 순회 순서는 0 - 1 - 2 - 3 - 4 - 5가 된다.

• 루트 노드의 0 방문
• 0이 루트 노드인 트리의 왼쪽 서브트리인 1을 방문 -> 1은 자식노드가 있으므로 1이 루트 노드인 서브트리 탐색
• 1이 루트 노드인 트리의 왼쪽 서브트리인 2를 방문 -> 2는 리프노드이므로 더이상 탐색 X
• 1이 루트 노드인 트리의 오른쪽 서브트리인 3을 방문 -> 3은 리프노드이므로 더이상 탐색 X
• 0이 루트 노드인 트리의 오른쪽 서브트리인 4를 방문  -> 4는 자식노드가 있으므로 4가 루트 노드인 서브트리 탐색
• 4가 루트 노드인 트리의 왼쪽 서브트리인 5를 방문 -> 5는 리프노드이므로 더이상 탐색 X
• 모든 노드를 방문하였으므로, 탐색 종료

그리고 이를 코드로 구현하면 다음과 같다.

visit = [False] * (n + 1) # 방문한 노드를 표시할 리스트 생성

# dfs 함수
def dfs(node):
  visit[node] = True # 방문 노드 True로 표시
  for i in graph[node]: # 방문한 노드의 모든 자식노드에 대해
    if not visit[i]: # 만약 아직 방문하지 않은 노드라면
      dfs(i) # 방문하지 않은 자식노드에 대해 dfs 실시

 

그리고, 해당 함수를 크게 두가지 경우로 나누어 활용해볼 수 있을 것 같다.

 

(1) 트리의 개수가 여러개일 때 >> 아마 이게 대부분

트리의 개수가 여러 개라는 의미는 이차원 배열 안에서 대각선, 양옆으로 움직일 수 있을 때, 움직일 수 있는 영역의 개수 정도로 표현되는 것 같다. 실제로 풀었던 문제를 예시로 들어보자면, 배추가 이차원 배열 안에 듬성듬성 심어져있는데 & 살충제의 효과가 대각선, 양옆까지만 있을 때, 모든 배추에 살충제의 효과를 주기 위해 필요한 살충제의 총 개수는 몇 개인가의 느낌 !

이럴때는 "연결된 그래프를 탐색하고 >> 탐색이 끝나면 count + 1 >> 다음 방문하지 않은 노드에 대해 dfs를 적용하여 노드와 연결된 그래프를 탐색하고 >> 탐색이 끝나면 count + 1"의 과정을 반복하면 된다. 그리고 그 과정은 다음과 같이 표현할 수 있다.

cnt = 0
for i in range(1, n + 1): # 모든 노드에 대해 반복문 실행
    if not visited[i]: # 방문하지 않은 노드이면
        if not graph[i]: # 정점은 존재하지만 & 연결된 정점이 없을 때 = 하나의 노드로 이루어진 그래프일 때
            cnt += 1 # count + 1
            visited[i] = True # 방문했다고 표시
        else: # 연결된 정점이 있으면
            dfs(i) # 노드에 대해 dfs 실행
            cnt += 1 # count + 1

print(cnt)

 

사실 아래처럼도 코드를 짤 수 있는데, 연결된 간선이 없는 정점에 대해 재귀함수를 굳이 호출할 필요는 없으니 위처럼 코드를 짜는게 더 효율적일 것 같다.

cnt = 0
for i in range(1, n + 1): # 모든 노드에 대해 반복문 실행
    if not visited[i]: # 방문하지 않은 노드이면
    	dfs(i) # 노드에 대해 dfs 실행
        cnt += 1 # count + 1

print(cnt)

 

(2) 트리의 개수가 하나일 때

그냥 가장 기본적으로 트리를 탐색하고자 할 때 사용할 수 있고, 시작노드만 아래처럼 지정해주면 된다.

dfs(1)

 

💡 BFS (너비 우선 탐색)

BFS는 이름 그대로 너비를 우선으로 탐색하는 방법이다. 레벨 순 순회라고도 할 수 있는데 쉽게 말하면 모든 노드를 낮은 레벨부터 차례대로 순회하는 방식이다. 0레벨의 노드를 탐색 -> 1레벨의 노드를 탐색 -> 2레벨의 노드를 탐색하는 식으로 !

출처 : https://velog.io/@tomist0930/dfs

예시를 통해 확인해보면, BFS의 순회 순서는 0 - 1 - 4 - 2 - 3 - 5 가 되고, DFS보다 훨씬 간단하다.

• 레벨 0의 0 탐색
• 레벨 1의 1 -> 4 탐색
• 레벨 2의 2 -> 3 -> 5 탐색
• 모든 노드를 방문했으므로 탐색 중지

그리고 이를 코드로 구현하면 다음과 같다.

from collections import deque

# 방문 노드 리스트 생성
visit = [False] * (n + 1)

# bfs 함수
def bfs(node):
  visit[node] = True # 시작 노드 방문
  queue = deque([node]) # queue 생성
  while queue: # queue에 원소가 포함되어 있는 동안
    v = queue.popleft() # queue의 가장 왼쪽의 값을 추출 (가장 최근에 추가된 값)
    for i in graph[v]: # v의 모든 자식노드에 대해
      if not visit[i]: # 방문하지 않은 노드는
        queue.append(i) # queue에 추가하고
        visit[i] = True # 방문했음을 표시해줌

 

재귀적으로 호출하며 실행되는 DFS와 달리 while문을 통해 실행되기 때문에 함수를 한 번만 호출하면 된다. 그래서인지, BFS와 DFS를 모두 사용하여 문제를 풀었을 때 BFS가 성능이 더 좋았던 적이 많았다. 풀이의 방식은 위의 DFS처럼 동일하게 트리가 여러 개일 때 & 한 개일 때로 나누어 활용할 수 있다. 설명은 위에 참고 !

 

(1) 트리의 개수가 여러개일 때 >> 아마 이게 대부분

cnt = 0
for i in range(1, n + 1): # 모든 노드에 대해 반복문 실행
    if not visited[i]: # 방문하지 않은 노드이면
        if not graph[i]: # 정점은 존재하지만 & 연결된 정점이 없을 때 = 하나의 노드로 이루어진 그래프일 때
            cnt += 1 # count + 1
            visited[i] = True # 방문했다고 표시
        else: # 연결된 정점이 있으면
            bfs(i) # 노드에 대해 bfs 실행
            cnt += 1 # count + 1

print(cnt)

 

 

(2) 트리의 개수가 하나일 때

bfs(1)

💡 탐색순서 : DFS & BFS 비교

• DFS : F - B - A - D - C - E - G - I - H
• BFS : F - B - G - A - D - I - C - E - H