[TAVE/파이썬 알고리즘 인터뷰] Ch12 | 그래프 - 개념 정리

참고자료 : 파이썬 알고리즘 인터뷰

✅그래프란?

👉🏻객체의 일부 쌍들이 연관되어 있는 객체 집합 구조

✍🏻쾨니히스베르크에 있는 섬과 도시를 연결하는 7개의 다리를 한 번씩만 건너서 모두 지나가는 해법을 찾으며 시작되었다.

오일러 경로

• A ~ D는 정점
• a ~ g는 간선

👉🏻오일러의 주장: 모든 정점이 짝수 개의 차수를 갖는다면 모든 다리를 한 번씩만 건너서 도달하는 것이 성립한다.

👉🏻오일러의 정리: 칼 히어홀저가 수학적으로 증명했다.

✍🏻쾨니히스베르크의 다리는 모든 정점이 짝수 개의 차수를 갖지 않으므로 오일러 경로가 아니다.

해밀턴 경로

👉🏻각 정점을 한 번씩 방문하는 무향 또는 유향 그래프 경로이다. 최적 알고리즘이 없는 대표적인 NP-완전 문제다.

👉🏻해밀턴 순환: 원래의 출발점으로 돌아오는 경로

👉🏻외판원 문제: 해밀턴 순환 중 최단 거리를 찾는 문제

 

✅NP복잡도

👉🏻비결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제의 집합이다.

그래프 순회

✅그래프(graph)

• 정점: 여러 가지 특성을 가질 수 있는 객체로, 노드라고도 부른다.
• 간선: 각 정점들의 관계를 나타낸 것이다.

🐰파이썬에서는 그래프를 주로 딕셔너리를 이용하여 나타낸다. 위의 그래프는 다음과 같이 나타낼 수 있다.

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

 

👉🏻그래프 순회란 그래프 탐색이라고도 부르는데 그래프의 각 정점을 방문하는 과정을 말한다.

• DFS: 깊이 우선 탐색
  • 주로 스택이나 재귀로 구현 → 더 간단한 재귀 선호
• BFS: 너비 우선 탐색
  • 주로 큐로 구현

 

✅DFS(깊이 우선 탐색)

👉🏻시작점의 자식을 탐색하고 자식의 자식을 탐색해 가장 깊이 있는 정점까지 탐색한다. 만약 정점에 자식이 없다면 이전 정점으로 돌아가 다시 탐색한다.

✍🏻위의 그래프 탐색법: 1 → 2 → 5 → 6 → 7 → 3 → 4

 

1️⃣재귀 구조로 구현

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

👉🏻v는 시작점(1번 정점)이고 discovered는 탐색한 정점들을 담는 리스트이다.

 

2️⃣스택을 이용한 반복 구조로 구현

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

👉🏻재귀 구현보다 직관적이고 실행 속도가 더 빠른 편이다.

 

✅BFS(너비 우선 탐색)

👉🏻출발 노드에서 인접한 노드를 탐색한다. 한 노드의 인접 노드의 처리가 끝나면 노드의 자식으로 내려가서 탐색을 시작하고, 자식의 인접 노드의 탐색이 끝나면 그 자식으로 내려가서 탐색한다.

✍🏻위의 그래프 탐색법: 1 → 2 → 3 → 4 → 5 → 6 → 7

1️⃣큐를 이용한 반복 구조로 구현

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

👉🏻탐색하는 노드를 순서대로 저장하는 discovered, 탐색하고 있는 노드의 인접 노드들을 저장해두는 queue를 이용한다.

✍🏻파이썬에서 pop(0)을 사용하면 리스트의 첫 번째 요소를 뺀 뒤 모든 요소들을 한 칸씩 앞으로 이동하기 때문에 복잡도가 증가한다. 때문에 데크를 이용해 큐를 구현하면 간단하고 획기적으로 속도를 증가시킬 수 있다.

2️⃣재귀 구현 불가

백트래킹(Backtracking)

👉🏻해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기(백트랙, Backtrack)해 정답을 찾아가는 범용적인 알고리즘이다. 제약 충족 문제에 특히 유용하다.

👉🏻DFS는 백트래킹의 골격을 이루는 알고리즘이다.

👉🏻운이 좋으면 최단 시행착오를 덜 거치고 목적지에 도착할 수 있지만 최악의 경우 모든 경우를 다 거쳐야 한다. 때문에 브루트 포스와 유사하다. 그러나 한번 방문 후 가능성이 없는 후보는 즉시 포기한다는 점이 프루트 포스와의 차이점이다.

👉🏻위와 같은 트리를 탐색할 때 가능성 없는 후보를 버리는 것을 트리의 가지치기라고 한다. 

제약 충족 문제

👉🏻수많은 제약 조건을 충족하는 상태를 찾아내는 수학 문제

👉🏻대표적인 예로 스도쿠가 있다.