[이코테] 5장 DFS/BFS

DFS/BFS

그래프를 탐색하기 위한 대표적인 두 가지 알고리즘

• 탐색 (Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 코딩 테스트에서 매우 자주 등장하는 유형
• 필요 자료구조 : 스택, 큐, 재귀함수

 

---

DFS (깊이 우선 탐색)

깊은 부분을 우선적으로 탐색하는 알고리즘

• 스택 혹은 재귀 함수를 이용

 

[동작 과정]

1. 탐색 시작 노드를 스택에 넣고 방문 처리를 한다.

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 1개라도 있으면, 그 노드를 스택에 넣고 방문 처리한다.

3. 방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼낸다.

4. 더 이상 2번 과정을 수행할 수 없을 때까지 반복

 

(방문 기준 : 번호가 낮은 순서)

 

• 시작 노드 : 1

 

 

 

# 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)

# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
	[],           # 시작 노드 : 1
    [2, 3, 8],    # 1번 노드의 인점 노드
    [1, 7],       # 2번 노드의 인접 노드
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]


# 각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9   # 처음엔 모두 False로 초기화
			# 인덱스 0을 사용하지 않기 위해 하나더 큰 공간 생성

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

 

 

 

---

BFS(너비 우선 탐색)

가까운 노드부터 탐색하는 알고리즘

- 큐 사용

 

[동작 과정]

1. 탐색 시작 노드를 큐에 넣고 방문 처리를 한다.

2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.

3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

 

(방문 기준 : 번호가 낮은 인접 노드부터)

• 시작 노드 : 1

 

• 거리가 가까운 순으로 방문 => 최단 거리 문제에 적용 가능

 

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
	# 큐 구현을 위해 deque 사용
    queue = deque([start])
    
    # 현재 노드를 방문 처리
    visited[start] = True
    
    # 큐가 빌 때까지 반복
    while queue:
    	# 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        
        # 아직 방문하지 않은 인접 노드를 큐에 모두 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True


# 각 노드가 연결된 정보(2차원 리스트)
graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

 

 

---

[ DFS와 BFS 차이 ]

 

출처 : 나무위키

 

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀 함수 이용	큐 이용(deque)