깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

GYUBIN ·2023년 1월 28일

코딩테스트 준비

목록 보기

10/10

DFS, BFS

1. 정의

깊이 우선 탐색(DFS)

Depth First Search.

한쪽 벽만 따라서 미로를 탈출하는 방법과 유사하다.
정점(node) 혹은 다른 임의의 노드에서 한 루트를 끝까지 탐색하고 다시 돌아가서 다른 루트를 탐색하는 방법이다.
주로 스택(FILO), 재귀함수를 통해 구현된다.
장점은 현재 루트 상의 노드만 저장하면 되기에 저장공간의 수요가 비교적 적다는 점이다.

너비 우선 탐색(BFS)

Breadth First Search.

정점(node) 혹은 다른 임의의 노드에서 인접한 모든 노드를 우선 탐색하는 방법이다.
주로 큐(FIFO)를 통해 구현되고, python으로 구현 시에는 deque를 사용한다.
장점은 출발 노드로부터 목표 노드까지의 최단 경로를 보장한다는 점이다.

2. 코드 구현

포스트 시작 부분에 있는 gif 파일을 코드로 만들어보자

깊이 우선 탐색(DFS)

graph = [
    [],         # 0
    [2, 4, 8],  # 1
    [1, 3],     # 2
    [2],  		# 3
    [1, 5, 7],  # 4
    [4, 6],     # 5
    [5], 	    # 6
    [4], 	    # 7
    [1, 9],     # 8
    [8], 	    # 9
]
visited = [False] * 10

def dfs(v):
    # v 방문
    visited[v] = True
    print(v, end=" ")
    # v의 인접 노드 확인
    for i in graph[v]:
        # i에 방문하지 않았으면
        if not visited[i]:
            # i 방문
            dfs(i)

dfs(1)  # 1 2 3 4 5 6 7 8 9

너비 우선 탐색(BFS)

graph = [
    [], 		# 0
    [2, 3, 4],  # 1
    [1, 5],  	# 2
    [1, 6, 7],  # 3
    [1, 8],     # 4
    [2], 		# 5
    [3, 9],     # 6
    [3],  		# 7
    [4],		# 8
    [6], 		# 9
]
visited = [False] * 10

def bfs(v):
    queue = deque([v])
    # v 방문
    visited[v] = True
    # 큐가 빌 때까지
    while queue:
        # 큐에서 노드를 하나 뺌
        v = queue.popleft()
        print(v, end=" ")
        # v의 인접 노드 확인
        for i in graph[v]:
            # i에 방문하지 않았다면
            if not visited[i]:
                # i 방문
                queue.append(i)
                visited[i] = True

bfs(1)  # 1 2 3 4 5 6 7 8 9

3. 예시 문제

백준 1260 - DFS와 BFS

예제 1

# 그래프 생성
n, v, m = 4, 5, 1
arr = ["1 2", "1 3", "1 4", "2 4", "3 4"]
graph = [[0] * (n + 1) for _ in range(n + 1)]
# graph = [
# 	  [0, 0, 0, 0, 0],
#     [0, 0, 0, 0, 0],
#     [0, 0, 0, 0, 0],
#     [0, 0, 0, 0, 0],
#     [0, 0, 0, 0, 0],
# ]
for i in range(m):
	a, b = map(int, arr[i].split())
    graph[a][b] = graph[b][a] = 1
# graph = [
# 	  [0, 0, 0, 0, 0],
#     [0, 0, 1, 1, 1],
#     [0, 1, 0, 0, 1],
#     [0, 1, 0, 0, 1],
#     [0, 1, 1, 1, 0],
# ]
visited = [0] * 5

깊이 우선 탐색(DFS)

def dfs(v):
    # v 방문
    visited[v] = 1
    print(v, end=" ")
    for i in range(1, n + 1):
    	# v의 인접 노드인 i에 방문하지 않았다면
        if graph[v][i] == 1 and visited[i] == 0:
            # i 방문
            dfs(i)

dfs(v)  # 1 2 4 3

너비 우선 탐색(BFS)

def bfs(v):
    queue = deque([v])
    # v 방문
    visited[v] = 1
    # 큐가 빌 때까지
    while queue:
        # 큐에서 노드를 하나 뺌
        v = queue.popleft()
        print(v, end=" ")
        for i in range(1, n + 1):
            # v의 인접 노드인 i에 방문하지 않았다면
            if graph[v][i] == 1 and visited[i] == 0:
                # i 방문
                queue.append(i)
                visited[i] = 1