[파이썬 알고리즘 인터뷰] 12장 그래프

그래프를 표현하는 방법은 크게 인접 행렬과 인접 리스트 2가지가 있다. 인접 리스트를 파이썬 딕셔너리 자료형으로 나타내면 다음과 같다.

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6. 7]
    6: [],
    7: [3],
}

 

DFS (깊이 우선 탐색)

일반적으로 DFS는 스택으로 구현하거나 재귀로 구현하며, 백트래킹을 통해 뛰어난 효용을 보인다. 코딩 테스트 시에 재귀 구현이 더 선호되는 편이다. 하지만 실행 속도는 스택을 이용한 구현이 더 빠른 편이다!

// 재귀를 이용한 DFS 구현

def dfs(v, discovered=[]):
    discovered.append(v)
    for w in graph[v]:
        if w not in discovered:
            discovered = dfs(w, discovered)
    return discovered

// 스택을 이용한 DFS

def dfs(start_v):
    discovered = []
    stack = [start_v]
    while stack:
        v = stack.pop()
        if v not in discovered:
            discovered.append(v)
            for w in graph[v]:
                stack.append(w)
    return discovered

 

BFS (너비 우선 탐색)

BFS는 주로 큐로 구현하며, DFS 보다 쓰임새는 적지만 최단 경로를 찾는 다익스트라 알고리즘 등에 매우 유용하게 쓰인다.

// 큐를 이용한 반복 구조로 구현

def bfs(start_v):
    discovered = [start_v]
    queue = [start_v]
    while queue:
    	v = queue.pop(0)
        for w in graph[v]:
        	if w not in discovered:
            	discovered.append(w)
    return discovered

 

백트래킹 (Backtracking)

백트래킹은 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기하고 왔던 길을 되돌아가 다른 정답을 찾아가는 범용적인 알고리즘으로 제약 충족 문제(Constraint Satisfaction Problems)에 특히 유용하다. 주로 재귀로 구현하며, 알고리즘마다 DFS 변형이 조금씩 일어나지만 기본적으로 모두 DFS 범주에 속한다. 한마디로 백트래킹은 가보고 되돌아오고를 반복한다! 최악의 경우 모든 경우를 다 거친 다음에야 정답을 찾을 수 있어 브루트 포스와 유사하다고 생각할 수 있지만, 한 번 방문 후 가능성이 없는 경우에는 즉시 후보를 포기한다는 점에서 매번 같은 경로를 반복하는 브루트 포스보다는 훨씬 더 우아한 방식이라고 할 수 있다.

 

 

☝🏻제약 충족 문제 (Constraint Satisfaction Problems, CSP)

수많은 제약 조건을 충족하는 상태를 찾아내는 수학 문제를 일컫는다. 대표적으로 스도쿠처럼 1에서 9까지 숫자를 한 번만 넣는(제약 조건 충족) 정답(상태)을 찾아내는 모든 문제 유형을 말한다.