파이썬 공부

[DFS/BFS] Chapter 05 DFS/BFS

지식보부상님 2025. 2. 5. 04:01

<이것이 취업을 위한 코딩테스트다 with 파이썬> 책의 내용을 정리한 것입니다.

 

스택(Stack) 은 FILO(First-In-Last-Out) 구조를 가진다.

이는 가장 나중에 들어온 데이터가 가장 먼저 삭제 되는 자료구조라는 의미이다.

파이썬에서 스택 자료구조를 구현하기 위해선, 

리스트에서 append() 와 pop() 매서드를 이용하면 구현 가능하므로, 별도의 라이브러리는 필요 없다.

 

큐(Queue)는 FIFO(First-In-First-Out) 구조를 가진다.

즉, 먼저 들어온 데이터가 먼저 삭제되는 자료구조이다.

파이썬에서 큐 자료구조를 구현할 땐 collections 모듈에서 제공하는 deque 자료구조를 활용하면 된다.

from collections import deque

queue = deque()
# 5삽입 - 2 삽입 - 삭제 - 1 삽입 - 삭제 
queue.append(5)
queue.append(2)
queue.popleft()
queue.append(1)
queue.append(3)
queue.popleft()

print(list(queue))  # [1, 3] 으로 출력됨

 

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

재귀함수를 이용할 때는, 재귀함수가 언제 끝날지 알려주는 종료 조건을 꼭 명시해야 한다.

컴퓨터 내부에선 재귀함수의 수행을 스택 자료구조로 이용한다. 

 

그래프는

인접 행렬(Adjacency Matrix): 2차원 배열로 그래프 연결관계 표현

인접 리스트(Adjacency List): 리스트로 그래프 연결관계 표현

으로 구현 가능하며, 노드 사이에 간선이 존재하지 않으면 무한(INF)으로  작성한다.

# 인접 행렬로 그래프 표현하기
INF = 987654321

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

 

# 인접 리스트로 그래프 구현하기
# 행이 노드개수인 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))

 

메모리 효율 : 인접 행렬 < 인접 리스트

순회 효율: 인접 행렬 > 인접 리스트

 

 

DFS(Depth-First Search) 는 깊이 우선 탐색이라고 부르며, 주로 스택을 이용하여 구현하는 알고리즘이다.

특정 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가 노드 방문 후, 다시 돌아가 탐색하는 알고리즘이다.

즉, 최대한 멀리 있는 노드를 우선적으로 탐색한다.

1. 탐색 시작 노드를 스택에 삽입 후 방문 처리
2. 스택의 최상단 노드(last)에 방문하지 않은 인접 노드가
 2-1. 있다면 그 인접 노드를 스택에 넣고, 방문 처리
 2-2. 없다면 스택에서 최상단 노드(last)를 꺼낸다.

 

위의 과정을 반복하면서 탐색하면 된다. 

이를 실제로 구현할 때 재귀함수를 이용하면 간결하게 구현가능하다.

# DFS 구현
def dfs(graph, v, visited):
    # 현재 노드는 방문 처리한다.
    visited[v] = True
    print(v, end=' ')

    # 인접 노드 재귀적으로 방문
    for w in graph[v]:
        if not visited[w]:
            dfs(graph, w, visited)


# 각 노드가 연결된 정보
graph = [[],
         [2, 3, 8],
         [1, 7],
         [1, 4, 5],
         [3, 5],
         [3, 4],
         [7],
         [2, 6, 8],
         [1, 7]
         ]

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

# dfs 함수 호출
dfs(graph, 1, visited)

 

BFS(Breadth First Search) 는 너비 우선 탐색으로, 가까운 노드부터 방문하는 알고리즘이다.

이는 큐 자료구조를 이용하여 주로 구현한다. 그 이유는 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색이 가능하기 때문이다.

1. 탐색 시작 노드를 큐에 삽입하고 방문처리
2. 큐에서 노드 꺼내 해당 노드와 인접한 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
3. 2번 과정 더이상 수행 불가할 때까지 반복

 

dequeue 라이브러리를 이용하면 탐색을 수행하는데 O(N)의 시간이 소요되며, 일반적으로 DFS 보다 실제 수행 시간이 좋은 편이다.

from collections import deque


# BFS 구현
def bfs(graph, start, visited):
    # 큐 구현
    queue = deque([start])
    # 현재 노드 방문처리
    visited[start] = True
    # 큐가 빌때까지 인접 노드 큐에 넣는 과정 반복
    while queue:
        # 큐에서 원소 하나 뽑음
        v = queue.popleft()
        print(v, end=' ')
        # v와 인접 노드 모두 큐에 삽입
        for w in graph[v]:
            if not visited[w]:
                queue.append(w)
                visited[w] = True

# 각 노드가 연결된 정보
graph = [[],
         [2, 3, 8],
         [1, 7],
         [1, 4, 5],
         [3, 5],
         [3, 4],
         [7],
         [2, 6, 8],
         [1, 7]
         ]

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

# bfs 함수 호출
bfs(graph, 1, visited)