ALGORITHM| graph(dfs, bfs, backtracking)
‘파이썬 알고리즘 인터뷰(박상길 지음)’
그래프
수학에서 좀 더 구체적으로 그래프 이론에서 그래프란 객체의 일부 쌍(pair)들이 연관되어 있는 객체 집합 구조입니다.
쾨니히스베르크의 다리문제: “이 7개 다리를 한 번씩만 건너서 모두 지나갈 수 있을까?”
오일러 경로
오일러 정리: 모든 정점이 짝수 개의 차수(Degree)를 갖는다면 모든 다리를 한 번씩만 건너서 도달하는 것이 성립합니다.
모든 간선을 한 번식 방문하는 유한 그래프(Finite Graph)를 일컬어 오일러 경로(Eulerian Trail/Eulerian Path)라 부르며 한붓그리기라고도 말합니다.
해밀턴 경로
해밀턴 경로: 각 정점을 한 번씩 방문하는 무향 또는 유향 그래프 경로입니다.
오일러 VS 해밀턴
- 오일러 경로: 간선을 기준
- 해밀턴 경로: 정점을 기준
이런 단순한 차이이지만 해밀턴 경로를 찾는 문제는 최적 알고리즘이 없는 대표적인 NP-완전 문제 중에서도 Hard합니다.
원래의 출발점으로 돌아오는 경로는 해밀턴 순환, 이중에서도 특히 최단 거리를 찾는 문제는 알고리즘 분야에서 외판원 문제(TSP; Travelling Salesman Problem)로도 더욱 유명합니다.
외판원 문제
각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 문제, 즉 최단 거리인 해밀턴 순환을 찾는 문제이며 NP-난해 문제로 매우 중요한 문제 중 하나입니다.
→ 만약 도시가 20개면 경로의 수는 20!, 240경 번의 경로를 다녀봐야 짧은 경로를 찾을 수 있습니다. 문제는 단순하지만 정답은 어마어마..
NP 복잡도
NP: 비결정론적 튜닝 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합입니다.
그래프 순회
그래프 탐색이라고 불리며 그래프의 각 정점을 방문하는 과정입니다.
그래프를 표현하는 방법
- 인접 행렬(Adjacentcy Matrix)
- 인접 리스트(Adjacency List)
graph = {
1: [2, 3, 4],
2: [5],
3: [5],
4: [],
5: [6, 7],
6: [],
7: [3],
}
→그래프를 인접 리스트로 표현합니다.
출발 노드를 키로, 도착 노드를 값으로 표현합니다. 도착 노드는 여러개가 될 수 있으므로 리스트 형태, 파이썬의 딕셔너리 자료형으로 다음과 같이 나타낼 수 있습니다.
DFS(깊이 우선 탐색)
재귀 구조
def recursive_dfs(v, discovered=[]):
discovered.append(v)
for w in graph[v]:
if w not in discovered:
discovered = recursive_dfs(w, discovered)
return discovered
[1, 2, 5, 6, 7, 3, 4]
스택을 이용한 반복 구조로 구현
def iterative_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
[1, 4, 3, 5, 7, 6, 2]
- 재귀 DFS는 사전식 순서로 방문한 데 반해 반복 DFS는 스택으로 구현되어 역순으로 방문했습니다.
- 인접 노드를 한꺼번에 추가하는 형태이기 때문에, 자칫 BFS가 아닌가 하고 헷갈릴 수 있지만 깊이 우선 탐색한다는 점에서 DFS가 맞습니다.
BFS(너비 우선 탐색)
큐를 이용한 반복 구조로 구현
스택을 이용하는 DFS와 달리, 큐를 이용합니다.
def iterative_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)
queue.append(w)
return discovered
[1, 2, 3, 4, 5, 6, 7]
재귀구조
BFS는 재귀 구조로 동작하지 않습니다.
백트래킹(Backtrank)
해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기(백트랙킹/ Backtrack)해 정답을 찾아가는 범용적인 알고리즘으로 DFS와 같은 방식으로 탐색하는 모든 방법을 말합니다.
- DFS는 백트래킹의 골격 (알고리즘마다 DFS 변형이 조금씩 일어나지만 기본적으로 모두 DFS의 범주에 속함)
- 주로 재귀로 구현
- 알고리즘마다 DFS 변형이 조금씩 일어나지만 기본적으로 모두 DFS의 범주에 속합니다.
- 백트래킹은 가보고 되돌아오기를 반복하므로 브루트 포스와 유사하지만 한번 방문하고 가능성이 없으면 즉시 후보를 포기(가지치기)한다는 점에서 브루트 포스보다는 훨씬 우아한 방식?입니다.
큰 트리가 있을 경우 브루트 포스로 전체 트리를 탐색한다면 매우 긴 시간이 소요, 하지만 DFS로 탐색을 하고 가능성이 없는 후보는 즉시 포기하고 백트래킹을 한다면 트리의 불필요한 요소를 버릴 수 있습니다. → 트리의 가지치기
이처럼 불필요한 부분을 일찍 포기한다면 탐색을 최적화할 수 있어서 가지치기는 트리의 탐색 최적화 문제와도 관련이 깊습니다.
제약 충족 문제(Constraint Satisfaction Problems; CSP)
제약 충족 문제란? 수많은 제약 조건을 충족하는 상태를 찾아내는 수학 문제입니다.
백트래킹은 CSP를 풀이하는데 필수적입니다.
대표적으로 스도쿠처럼 1에서 9까지 숫자를 한번만 넣는(제약조건충족) 정답(상태)을 찾아내는 모든 문제 유형을 말합니다.
DFS VS BFS 선택 기준
DFS
- 연결된 그래프를 완전 탐색하는데 활용가능
- 모든 경우를 하나하나 다 탐색을 해야될경우 이용(조합, 순열 모든 경우의 수를 하나하나 다 찾고자 할 때)
- 위의 개념과 결부된 깊이 우선 탐색이라는 개념을 가진 순열, 조합 구현에 활용
BFS
- DFS와 마찬가지로 연결된 그래프를 완전탐색하는데 활용
- depth(깊이)를 계산해야되는 문제에 활용(위의 문제 예의 경우 최단 경로의 길이 == depth(깊이))
- 위의 개념과 결부된 가중치가 같은 그래프에서 최단거리를 찾는데 활용
