알고리즘에서 그래프는 실제 세계의 현상이나 사물을 정점, 노드, 간선으로 표현하여 나타내기 쉽다. 따라서 경로, 방법 탐색 등의 각종 문제 해결의 상황에서 자주 활용된다. 본 포스팅에서는 그래프와 관련된 기초 용어는 다루지 않으니 궁금한 사람은 구박사님(=구글링)께 물어보도록 하고, 그래프 공부를 하며 정리하는 과정에서 얻은 insight를 공유하고자 한다.
1. BFS(너비 우선 탐색 = 형제 우선)
- 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식
- 그래프를 나타내기 위해 각 노드를 Key, 그리고 각 key와 간선으로 연결된 노드를 관리하는 list를 value로 가지는 map활용
- 앞으로 방문할 노드를 관리하는 큐(need_visit), 방문했던 노드를 관리하는 큐(visited), 이렇게 총 2개의 큐를 활용하여 구현
- 방문할 노드를 선입선출로 관리(상위 level부터 조회)해야하므로 큐 자료구조를 활용한다.
2. DFS(깊이 우선 탐색 = 자식 우선)
- 정점의 자식 노드들을 먼저 탐색하는 방식
- 그래프를 나타내기 위해 BFS와 동일한 K, V를 갖는 map활용
- need_visit은 스택, visited는 큐를 활용하여 구현
- need_visit에 put되는 순서로 따지면 상위 레벨(형제노드)의 노드가 먼저이지만, 하위 레벨의 노드(자식노드)가 먼저 조회되어야 하므로 need_visit을 스택으로 구현한다.
- DFS는 백트래킹 알고리즘에서도 활용된다. 백트래킹 알고리즘은 특정 조건들을 순차적으로 체크하여 이들을 만족하는 해를 찾아야하는 상황에서, 해를 찾기 위해 조건들을 점진적으로 확인하다가 특정 조건을 만족할 수 없다고 판단하는 즉시 backtrack(뒤로 물러서)하고 다음 조건을 확인하는 과정을 반복하여 최적의 해를 찾는 방법이다. 따라서 각 조건Case들을 트리(상태공간트리, State Space Tree)로 표현한다면 DFS방식으로 조건들을 확인해나가면 된다. 해를 구하는 방법이 대표적으로 두가지 있는데, 첫번째는 해당 루트가 조건에 맞는지를 검사하는 Promising기법, 두번째는 조건에 맞지 않으면 포기하고 다른 루트로 돌아서서 검사하는 Pruning기법이 있다.
3. 시간 복잡도
결국엔 need_visit이 empty상태가 될 때까지 visited, need_visit에 데이터를 추가하는 일련의 과정을 반복한다.
따라서 노드의 수를 V, 간선의 수를 E로 나타낼 때 O(V+E)의 시간복잡도가 나타난다.
4. 탐욕 알고리즘(Greedy Algorithm)
완벽한 최적의 해를 구하는 것 보단, 매 순간 최적이라고 생각되는 경우를 선택해서 최적의 해의 근사치를 빠르게 찾아내는 것에 focusing된 알고리즘이다. 우선순위를 정해서 각 단계별로 최적해를 구해나가는 방식이라고 생각하면 편할까? 예를 들어보자. 5810원의 금액을 최소한의 동전을 활용해서 지불해야한다. 그럼 당연히 500원, 100원, 50원, 10원 순으로 동전의 수가 많으면 된다. 동전의 종류를 우선순위 단계라고 생각하고 각 동전별(단계별) 동전의 개수(최적해)를 찾는 과정이 바로 탐욕 알고리즘이다.
5. 최단 경로 알고리즘 (다익스트라 알고리즘)
최단 경로 알고리즘은 그래프 상에서 두 노드를 잇는 가장 짧은 경로를 찾는 문제를 해결하는 알고리즘이며, 그 중 대표적인 알고리즘이 다익스트라 알고리즘이다. 문제해결의 concept은 가중치 그래프(각 간선에 가중치가 있는 그래프)에서 간선의 가중치 합이 최소가 되도록 하는 것이다.
5-1. 최단 경로 문제의 종류
- 단일 출발 단일 도착 최단 경로: 특정 노드 u에서 또 다른 특정 노드 v까지 도착하는 최단 경로를 찾는 문제
- 단일 출발 최단 경로: 특정 노드 u에서 그래프 내의 모든 다른 노드 v 각각의 최단 경로를 찾는 문제
- 전체 쌍 최단 경로: 그래프 내의 모든 노드 쌍(from u to v)에 대한 최단 경로를 찾는 문제
5-2. 다익스트라 알고리즘
- 위 문제 종류 중 두 번째인 단일 출발 최단 경로 문제를 해결하기 위한 알고리즘이다.
- 준비물: 첫 정점(u)부터 각 노드(v)간의 거리를 저장할 배열, 방문할 노드를 저장할 우선순위 큐
- 첫 정점(u)의 인접 노드들(u') 간의 거리부터 먼저 계산하여, 기존의 u-u' 거리보다 짧을 경우 위 배열에 업데이트한다.
- 인접노드 u'를 우선순위 큐에 저장한다.
- 첫 정점(u)와 인접한 노드들을 순차적으로 방문하기에 BFS와 Concept이 유사하다.
- 첫 정점과 인접 노드간의 거리를 우선 계산하되(BFS), 최단 거리의 노드를 우선 poll(우선순위 큐) 함으로써 최단 거리를 먼저 계산할 수 있도록 한다.
Step 0, 그래프 예시
Step 1, 준비물 초기화
- 거리 저장 배열: 첫 정점(A) 거리는 0, 나머지 노드까지의 거리는 inf(최댓값)로 저장
- 우선순위 큐: (첫 정점, 0) 저장
Step 2, 우선순위 큐에서 poll한 노드와 인접 노드간의 거리 계산
- 첫 정점 A와 인접 정점 A'간의 간선(거리)길이와 거리 저장 배열의 값을 비교해서 간선 값이 더 작을 경우 배열 업데이트
- 업데이트 된 경우, 해당 노드를 우선순위 큐에 삽입
- 첫 정점 A와 가장 가까운 거리의 노드인 C가 우선으로 poll됨
Step 3, 우선순위 큐에서 poll한 노드와 인접 노드간의 거리 계산(2) 반복
- 앞선 상황에서 A-B간의 최단 거리는 8이었지만, A-C-B로 올경우 6으로 새로운 최단 거리 탄생
- 거리 저장 배열을 업데이트하고, (해당 노드, 간선 값) 우선순위 큐에 삽입
- 우선순위 큐의 (B,8)은 어차피 후에 poll되더라도 최단 거리가 존재하기에 무시됨
+ insight
첫 정점 u에서 특정 노드 v까지의 최단거리 u-v는 v직전의 노드까지의 최단 경로를 포함하고 있다. 좀 더 쉽게 말해볼까. 위 그래프에서 노드 A에서 노드 F까지의 최단 경로는 A-D-E-F이다. 이는 A에서 E까지의 최단 경로를 포함하고 있고, A-E는 A에서 D까지의 최단 경로를 포함하고 있다. 이를 다르게 말하자면, 최단 거리 값에 이전에 방문한 노드명을 저장하면 최단 거리뿐만 아니라 최단 경로도 구할 수 있다. distances배열에 (최단경로, 이전 방문 노드)를 저장하면 된다는 뜻이다.
5-3. 다익스트라 알고리즘 시간 복잡도
과정1, 각 노드의 인접 간선을 모두 검사하는 과정
-> 그래프의 모든 간선은 최대 한 번만 검사하므로 O(E)
과정2, priority queue에 노드/거리 정보를 넣고 pop하는 과정
-> Priority queue에 가장 많은 노드가 들어가는 최악의 시나리오는 그래프의 각 간선이 검사될 때마다(과정1) 배열의 최단 거리가 갱신되고, priority queue에 노드가 추가되는 case이다. 따라서 시간 복잡도는 [배열의 최단 거리 갱신 * priority queue에서 minHeap을 유지]로 나타낼 수 있으므로 O(ElogE)이다.
총 시간 복잡도 = O(E) + O(ElogE) = O(ElogE)
'CS Engineering. > ALGORITHM' 카테고리의 다른 글
| 쓰이는 알고리즘 - 우선순위 큐(Heap)의 임의 요소 삭제에 관한 Idea (0) | 2021.03.17 |
|---|---|
| 쓰이는 알고리즘 - 그래프 기초(최소신장트리) (0) | 2021.03.17 |
| 쓰이는 알고리즘 - Recursive Call (재귀 호출) 언제 쓸까? (0) | 2021.01.27 |
| 쓰이는 자료구조 - Tree, Heap (Hash와 Tree의 성능비교 포함) (0) | 2021.01.26 |
| 쓰이는 자료구조 - Hash Table (1) | 2021.01.25 |