1. 탐색(Search)이란

• 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 대표적인 그래프 탐색 알고리즘으로 DFS, BFS를 꼽을 수 있다.
• 코딩 테스트의 주요 알고리즘으로 반드시 숙지해야 한다!!

2. 스택(Stack)

• 먼저 들어간 데이터가 나중에 나오는 자료구조이다.(LIFO)

• DFS 알고리즘에 사용된다.

  • 스택 삽입 과정

    

  • 스택 삭제 과정

    

2.1 재귀 함수

• 컴퓨터가 연속적으로 함수를 호출하게 되면 이는 컴퓨터 메모리 내부의 스택 프레임에 쌓인다.
• 따라서 스택을 사용해야 할 경우 구현상 스택 대신 재귀 함수를 사용하는 경우가 많다.
• DFS를 간결하게 작성하기 위해 재귀 함수를 활용하여 구현하기도 한다.
  

3. 큐(Queue)

• 먼저 들어간 데이터가 먼저 나오는 자료구조이다.(FIFO)

• BFS 알고리즘에 사용된다.

  • 큐 삽입 과정

    

  • 큐 삭제 과정

    

• 파이썬에서는 큐를 구현하기 위해 deque 라이브러리를 사용한다.

from collections import deque

q = deque()
# 삽입
q.append(1)
# 삭제
q.popleft()

4. DFS(Depth First Search)

• 현재 탐색중인 그래프 경로의 가장 깊은 곳까지 탐색한 후 다른 루트로 다시 탐색하는 방식이다.
• 스택 또는 재귀 함수를 활용하여 구현한다.
• 동작 과정
  1. 탐색을 시작할 노드를 스택에 삽입해 방문 처리한다.
  2. 스택 최상단에 있는 노드에 방문하지 않은 인접 노드가 있다면 해당 인접 노드를 스택에 넣고 방문 처리한다. 만약 방문하지 않은 인접 노드가 없다면 스택에서 최상단에 있는 노드를 꺼낸다.
     * 인접한 노드의 방문 순서 기준은 문제마다 다를 수 있지만, 일단 번호가 낮은 인접 노드부터 방문한다고 가정한다.
  3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

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, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드의 방문정보 저장
visited = [False] * 9

dfs(graph, 1, visited)

5. BFS(Breadth First Search)

• 탐색을 시작하는 노드에서 인접한 노드들을 우선적으로 탐색하는 방식이다.
• 큐를 활용하여 구현한다.
• BFS는 특정 조건에서의 최단 경로를 구하기 위한 목적으로도 효과적으로 사용이 가능하다.
• 동작 과정
  1. 탐색을 시작할 노드를 큐에 삽입해 방문 처리한다.
  2. 큐에서 노드를 꺼내고 해당 노드의 인접 노드 중 방문하지 않은 노드들을 모두 큐에 삽입한 후 방문 처리한다.
  3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

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)

그림 폰트 출처: 제주특별자치도, 제주서체, https://www.jeju.go.kr/jeju/symbol/font/infor.htm
참고 서적: 이것이 취업을 위한 코딩 테스트다 with 파이썬, 나동빈, 한빛미디어
참고 강의: 나동빈님 유튜브 강의