[알고리즘] DFS(Depth-First Search)/BFS(Breath First Search)

오늘은 DFS/BFS에 대한 포스팅이다. 맨날 코딩테스트 때만 바짝 외워서 문제 풀고 이래가지고 자주 까먹는 알고리즘 1위라 다시 복습하는 중이다...

---

그래프(Graph)

그래프는 노드(Node)와 간선(Edge)로 표현되는 구조이며, 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다' 라고 표현한다. 

그래프 표현 방식

그래프는 크게 두 가지 방식으로 표현할 수 있다.

• 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현하는 방식
• 인접 리스트(Adjacency List): 리스트로 그래프의 연결 관계를 표현하는 방식

graph1

	0	1	2
0	0	7	5
1	7	0	INF
2	5	INF	0

인접 행렬 방식 예제 (graph1 그림) 

INF = 99999999 # 무한의 비용 선언

# 2차원 리스트를 이용해 인접 행렬 표현
# 리스트[idx]의 값은 해당 idx 노드와의 거리 의미
graph = [
    [0, 7, 5], # [0번 노드와의 거리, 1번 노드와의 거리, 2번 노드와의 거리] 
    [7, 0, INF],
    [5, INF, 0]
]

인접 리스트 방식 예제 (graph1 그림) 

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

두 방식 비교

	인접 행렬	인접 리스트
메모리 측면	비효율적 모든 관계를 저장하므로 메모리가 불필요하게 낭비됨	효율적 연결된 정보만을 저장하기 때문에 효율적
속도 측면	빠름 연결 관계를 알고자 하는 노드 정보에 바로 접근할 수 있음	느림 연결된 데이터를 하나씩 확인해야 함

 

DFS(Depth-First Search)

깊이 우선 탐색 알고리즘으로, 특정한 노드에서 시작해(일반적으로는 루트 노드) 해당 분기를 최대한 깊숙히 탐색한 후 다음 분기로 넘어가는 방식으로 탐색하는 알고리즘이다. 

출처: https://developer-mac.tistory.com/64

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)
            
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

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

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

## output: 1 2 7 6 8 3 4 5

BFS(Breath First Search)

너비 우선 탐색 알고리즘으로, 가장 가까운 노드부터 탐색하는 알고리즘이다. 

출처: https://developer-mac.tistory.com/64

 

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 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

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

## output: 1 2 3 8 7 4 5 6

 

DFS, BFS 요약 정리

	DFS	BFS
사용하는 경우	모든 경우의 수를 구해야 하는 문제	최단거리 문제
검색 속도(일반적)	느림	빠름
동작 원리	스택	큐
구현 방법	재귀 함수 이용	큐 자료구조 이용