그래프 탐색 알고리즘 (DFS / BFS)

Stack (스택 자료구조)

1) 먼저 들어간 데이터가 나중에 나가는 자료 구조 (선입후출)

2) 구성 : 삽입 & 삭제

    - list(), append(), pop()을 사용

    - list[::-1] : 최하단 원소부터 출력

    - list : 최상단 원소부터 출력

 

Queue (큐 자료구조)

1) 먼저 들어간 데이터가 먼저 나가는 자료 구조 (선입선출)

2) 구성 : from collections import deque 라이브러리 사용

    - queue = deque() : 큐 구현

    - queue.append()

    - queue.popleft() : 먼저 들어간 데이터 뽑아내기

    - queue.reverse() : 역순

3) 억지로 리스트 자료형을 사용하지 말고 라이브러리를 사용하여 시간복잡도를 줄인다.

 

Recursive Function (재귀 함수)

1) 자신을 다시 호출하는 함수를 의미

2) stack과 비슷한 방식으로 동작한다.

 

3) 샘플문제

    - factorial

# for문
def get(n):
    result = 1
    
    for i in range(1, n + 1):
        result *= i
        
    return result

# 재귀함수
def fac(n):
    if n <= 1:
        return n
        
    return n * fac(n - 1)

 

4) 샘플문제

    - 최대공약수 계산 (유클리드 호제법)

    - 두 수 a, b에 대하여 a를 b로 나눈 나머지를 R

    - a, b의 최대공약수 = b, r의 최대공약수

def jose(a, b):
    if a % b == 0:
        return b
        
    else:
        r = a % b
        return jose(b, r)

---

그래프 탐색 알고리즘

1) 개요

    - 많은 양의 데이터 중 원하는 데이터를 찾는 과정

    - 대표적으로 DFS / BFS가 있는데 자주 등장

 

DFS (Depth-First Search)

1) 깊이 우선 탐색

2) stack 또는 재귀함수를 이용하여 동작

    - 탐색 시작 노드를 스택에 삽입하고 방문 처리

    - 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리

       (여러 개면 가장 작은 것).      단, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄

    - 2 번 과정을 수행할 수 없을 때까지 반복

 

3) 샘플문제

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

visited = [False] * 9

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

dfs(graph, 1, visited)

 

BFS (Breadth-First Search)

1) 너비 우선 탐색 (가까운 노드부터 탐색하는 알고리즘)

2) Queue를 이용하여 동작

    - 탐색 시작 노드를 큐에 삽입하고 방문 처리

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

    - 2 번 과정을 수행할 수 없을 때까지 반복

 

3) 샘플문제

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

visited = [False] * 9

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
    
bfs(graph, 1, visited)

---

나동빈님의 유튜브를 보고 정리한 내용입니다. www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2