[이것이 코딩테스트다 with 파이썬] bfs/dfs

최근 보고 있는 책인  '이것이 코딩테스트다 with 파이썬 편_나동빈_한빛미디어' 책을 읽으면서 정리하고자 한다.

www.hanbit.co.kr/store/books/look.php?p_code=B8945183661

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다.

이는 그래프, 트리 등의 자료구조 안에서 다루는데 대표적으로 dfs, bfs가 있다.

 

dfs, bfs 를 알기 위해서는 스택과 큐와 더불어서 재귀함수에 대한 개념이 잡혀있어야 한다.

재귀 함수에서 주의할 점은 '종료조건' 이 있어야 한다는 것이다!! 

 

 

DFS

DFS 는 깊이 우선 탐색으로, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 

그래프 : 노드(정점)와 간선으로 표현된다. 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다' 라고 표현한다.

 

 - 인접행렬 (Adjacency matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식

 - 인접 리스트 (Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식

 

# 인접 행렬 방식 예제

INF = 9999999999 # 무한의 비용 선언

graph = [

[0,7,5],

[7,0,INF],

[5,INF,0]

]

(연결관계)

 0-> 7-> 5

 7 -> 0

 5 -> 0

 

# 인접 리스트 방식 예제
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)

# [[(1,7), (2,5)], [(0,7)], [(0,5)]]

 

	메모리 측면	속도 측면
인접 행렬 방식	노드 개수가 많을 수록 불필요하게 낭비된다.	속도가 빠르다.
인접 리스트 방식	연결된 정보만을 저장하므로 메모리를 효율적으로 사용한다.	속도가 느리다.

 

노드 1과 노드 7이 연결되어 있는 상황이라면, 인접 행렬 방식은 graph[1][7]만 확인하면 되지만, 인접 리스트 방식에서는 노드 1에 대한 인접 리스트를 앞에서부터 찾아야 한다.

 

dfs의 동작과정

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

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면, 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드까지 꺼낸다.

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

 

이에 대한 그림은 책에 자세히 나와있다 !!

 

이는 stack 자료구조에 기반한다는 점에서 구현이 간단하다. 데이터의 개수가 N개인 경우 O(N)의 시간 복잡도를 가진다.

def dfs(graph, v, visited) :
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v] :
        if not visited[i] :
            dfs(graph, i, visited)


# 각 노드가 연결된 정보를 리스트 자료형으로 표현

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

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

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

 

 

BFS

너비 우선 탐색으로 가까운 노드부터 탐색하는 알고리즘이다. 선입 선출 방식인 queue 자료구조를 이용한다.

 

BFS 동작 과정

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

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

-> 빠지면서 인접 노드를 다 넣는다.

3. 2번의 과정을 수행할 수 없을 때 까지 반복한다.

 

이에 대한 그림 또한 책에 자세하기 나와있다.

이는 deque 라이브러리를 사용하는 것이 좋고 시간 복잡도는 O(N)이다. 실제 수행 시간은 BFS보다 좋은 편이다.

 

이는 코드로 작성하면 다음과 같다.

from collections import deque

# BFS method
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
                

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

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

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

 

 

 

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀함수 이용	큐 자료구조 이용

 

게임 맵이 나오고 상하좌우로 움직일 수 있는 경우, 그래프로 맵을 바꾸어 생각하면 bfs, dfs를 통해 탐색이 가능하다.

 

bfs. dfs는 항상 봐도 헷깔리기 때문에 책에서 제시한 방법을 완벽하게 숙지하고 응용해야겠다 !!