[이코테] chapter05 DFS/BFS

아래 글은 [이것이 코딩 테스트다 wiht 파이썬] 책을 기반하여 작성한 글입니다.

 

DFS/BFS

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

앞서 배운 chapter03 그리디, chapter04 구현 알고리즘과 달리 이번 챕터는 이론 공부가 중요하다.

(1) 배경 지식

    ● 탐색(search): 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

 

    ● 자료 구조(data structure): 데이터를 표현하고 관리하고 처리하기 위한 구조

        탐색 알고리즘에서 자주 사용하는 자료구조인 스택과 큐에 대해 알아보도록 하겠다.

        두 자료구조는 모두 삽입(push), 삭제(pop) 두 핵심 함수로 구성된다.

 

    ● 스택(stack): #박스_쌓기   #First_In_Last_Out

       파이썬에서는 스택을 이용할 떄에는 별도의 라이브러리를 사용할 필요가 없다.

       append()와 pop()함수로 삽입과 삭제가 가능하다.

 

    ● 큐(queue):  #대기줄   #First_In_First_Out   #공정한_자료구조

       파이썬에서는 큐를 구현할 때 collections 모듈에서 제공하는 덱(deque) 자료구조를 활용한다.

       덱은 스택과 큐의 장점을 모두 채택한 것인데, 이는 데이터를 넣고 빼는 속도가 리스트 자료형보다 효율적이다.

       그래서 queue 라이브러리를 이용하는 것보다 더 간단하다.

       append(), pop(), appendleft(), popleft()함수로 삽입과 삭제가 가능하다.

      추가적으로 deque 자료구조를 리스트로 사용하고 싶으면 list(deque)와 같이 사용하면 된다.

 

    ● 재귀 함수(Recursive Function):자기 자신을 다시 호출하는 함수 

       재귀함수를 사용할 때는 함수의 종료 조건을 꼭 명시해야 한다.

       반복문보다 재귀함수을 사용하면 코드가 더 간단해지는 이유: 점화식을 그대로 소스코드로 옮겼기 때문!

       (점화식이란 특정 함수를 자신보다 더 작은 변수에 재한 함수와의 관계로 표현한 것!)

점화식의 예

    ● 그래프(Graph)

       노드(node)와 edge(간선)으로 표현된다. 여기서 노드는 정점(vertex)라고도 불린다.

       "인접하다(Adjacent)": 두 노드가 간선으로 연결되어 있을 때.

       그래프의 두가지 표현 방법은 다음과 같다.

그래프1

그래프1에 대한 가중치표

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

INF = 9999999999

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

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

graph = [[] for _ in range(3)]

graph[0].append((1,7))
graph[0].append((2,5))

graph[1].append((0,7))

graph[2].append((0,5))

      메모리 측면에서는 인접 행렬 방법이 불필요하게 정보를 두배 저장하므로 좋지 않다.

      속도 측면에서는 인접 리스트 방법이 연결 여부를 아는데에 더 오래걸려 좋지 않다.

 

(2) DFS

🔍Depth-First Search, 깊이 우선 탐색
: 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

    ● 동작 원리: 스택

    ● 동작 구현: 재귀 함수 이용

    ● 동작 과정:

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

step2) 스택의 최상단 노드에 방문하지 않은 인접노드가 있으면,

그 인접 노드를 스택에 넣고 방문처리를 한다.

없으면, 스택에서 최상단 노드를 꺼낸다.

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

    ● DFS 예제 코드

def dfs(graph, v, visited):
    # 실제 동작 부분 start
    visited[v] = True
    print(v, end=' ')
    # 실제 동작 부분 end
    
    # 재귀를 위한 부분    
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

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

visited = [False] * 9

dfs(graph, 1, visited)

 

(3) BFS

🔍Breadth-First Search, 너비 우선 탐색
: 가까운 노드부터 탐색하는 알고리즘

    ● 동작 원리: 큐

    ● 동작 구현: 큐의 자료구조 이용

    ● 동작 과정:

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

step2) 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를

모두 큐에 삽입하고 방문 처리한다.

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

    ● BFS 예제 코드

from collections import deque

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)

코딩 테스트 중 2차원 배열에서의 탐색 문제를 만나면 그래프 형태로 바꿔 생각하면 풀이 방법을 조금 더 쉽게 떠울릴 수 있다!