DFS/BFS 간단 정리 (DFS,BFS/이론)

그래프의 기본 구조

그래프는 노드와 간선으로 표현되며 이때 노드를 정점이라고도 한다. 

그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 탐색하는 것을 말하는데 두노드가 간선으로 연결되있을 경우 '두 노드는 인접하다' 라고 말할 수 있다. 

 

프로그래밍레서 그래프는 크게 두가자 방식으로 표현할 수 있다.

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

 

인접 행렬

연결되어있지 않은 노드는 무한의 비용이라고 작성한다. 

 

INF = 999999999

graph = [
	[0, 7, 5],
    [7, 0 , INF],
    [5, INF, 0]
]

print(graph)

 

인접리스트

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

print(graph)

 

인접 행렬과 인접 리스트 비교

인접행렬은 모드놘계를 저장하는데 반해 인접리스트는 연결관계만 저장하기 때문에 인접리스트가 메모리를 더 효율적으로 사용한다. 하지만 특정 정보를 찾는데 있어서는 인접리스트는 데이터를 앞에서 부터 확인해야하지만 인접행렬은 바로 확인 가능하기때문에 (ex. graph[1][7]) 인접행렬이 더 정보를 얻는 속도가 빠르다.

• 정보를 얻는 속도 (인접리스트 < 인접행렬)'
• 메모리 효율 (인접리스트 > 인접행렬)

---

DFS

DFS는 깊이우선탐색이라고 부른다. (dept-First Search)

DFS는 최대한 깊게 들어가는 것을 목표로 두고 있다고 생각하면 쉽다. 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)

BFS

BFS는 너비 우선탐색이러고 부른다. (Breadth First Search)

BFS는 가까운 노드부터 탐색하는 방식이다. BFS는 큐 자료구조에 기초한다. 

 

from collections import deque
#큐 구현을 위해 deque라이브러리 사용

#BFS메서드 구현
def bfs(graph, start, visited):
    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


graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9

bfs(graph, 1, visited)

 

---

보통 코딩테스트에서 DFS보다는 BFS가 더 빨리 돌아가는 편이다.!