CS/스터디
[10주차] DFS&BFS, Greedy 알고리즘, 최소 신장 트리
spring_sunshine
2023. 3. 27. 10:13
DFS & BFS
- 그래프 알고리즘으로, 경로를 찾는 문제 시 상황에 맞게 DFS와 BFS를 활용하면 된다.
- 그래프는 정점(node)와 그 정점을 연결하는 간선(edge)로 이루어진 자료구조이며, 그래프를 탐색한다는 것은 하나의 정점에서 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.
- 두 알고리즘 모두 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. (검사하지 않을 경우 무한루프 위험성)
깊이 우선 탐색 (DFS)
- 루트 노드(혹은 임의의 노드)에서 시작해서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법 (미로찾기와 유사)
- 스택 또는 재귀함수로 구현 (순환 알고리즘의 형태)
- 모든 경로를 방문해야 할 경우에 적합
- 시간 복잡도 (V는 정점, E는 간선)
- 인접 행렬: O(V^2)
- 인접 리스트: O(V+E)
넓이 우선 탐색 (BFS)
- 루트 노드(혹은 임의의 노드)에서 인접한 노드부터 먼저 탐색하는 방법
- 큐를 이용하여 구현 (해당 노드의 주변부터 탐색해야 하기 때문) → 선입선출(FIFO) 원칙으로 탐색
- 최소비용이 우선일 때에 적합
- 주로 두 노드 사이의 최단 경로를 찾을 때 사용
- 재귀적으로 동작x
- 시간 복잡도
- 인접 행렬: O(V^2)
- 인접 리스트: O(V+E)
Greedy 알고리즘
- 탐욕 알고리즘
- 문제 해결을 위해 순간순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법
- 문제의 성질이 동일하게 보존되고, 같은 전략을 반복적으로 사용 가능할 때 적용
- 앞의 선택이 이후의 선택에 영향을 주지 않을 때
- 최종 해결 방법이 부분 문제에 대한 해결 방법과 동일한 조건일 때 (지역적, 전역적으로 모두 최적)
- 장점: 다른 최적 해 계산 알고리즘에 비해 적은 비용 (빠른 속도)
- 단점: 당장 그 순간의 최적 값을 찾기 때문에 항상 최적 해를 찾는 것은 불가능
- 문제 해결 방법
- 션택 절차: 현재 상태에서의 최적의 해답을 선택
- 적절성 검사: 선택된 해가 문제의 조건을 만족하는지 검사
- 해답 검사: 원래의 문제가 해결됐는지 검사하고, 해결되지 않았다면 다시 선택 절차로 돌아가 위의 과정 반복
최소 신장 트리 (Minimum Spanning Tree)
- 대표적인 알고리즘으로 프림 알고리즘, 크루스칼 알고리즘이 있다.
- 신장 트리는 그래프 내에 있는 모든 정점을 연결하면서 사이클이 없는 그래프를 의미한다.
- 최소 신장 트리는 간선들의 가중치의 합이 최소가 되는 신장 트리이다.
- 특징:
- 간선의 가중치의 합이 최소여야 한다.
- n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
- 사이클이 포함되어서는 안된다.
크루스칼 알고리즘
- 그래프 내의 모든 간선의 가중치를 확인하고, 가장 작은 가중치부터 확인하여 최소 신장 트리를 만드는 방법이다. 탐욕적인(Greedy) 방법을 사용한다.
- 동작 원리
- 선택되지 않은 간선들 중 최소 가중치인 간선을 선택한다. (모든 간선의 가중치를 오름차순으로 정렬 후)
- 그 간선을 선택했을 때 지금까지 구성된 스패닝 트리에 사이클이 없는 경우에만 선택한다.
- 총 (정점의 개수-1)개의 간선이 선택될 때까지 반복한다.
- 구성한 스패닝 트리에 사이클이 발생하는지 여부를 판단하기 위해 분리 집합을 사용한다. (분리집합: 서로 공통된 원소를 갖지 않는 집합)
- 이를 실제로 구현하기 위해선 Union-Find 알고리즘을 사용한다.
- 각 간선이 스패닝 트리에 추가될 때마다 Parent 관계를 만들어 놓는다.
- 만약 어떤 간선을 선택했을 때 그 간선의 두 정점이 같은 최상위 Parent를 갖는다면 사이클이 발생함을 의미한다.
프림 알고리즘
- 최소 신장 트리에 연결된 정점 주변에 있는 간선의 가중치 중 가장 작은 것을 골라 최소 신장 트리를 만드는 방법
- 동작 원리
- 그래프와 비어있는 최소 신장 트리를 만든다.
- 임의의 정점을 시작 정점으로 선택하고, 최소 신장 트리의 루트 노드로 삽입한다.
- 최소 신장 트리에 삽입된 정점과 이 정점과 인접한 정점의 가중치를 확인하여 가장 작은 가중치를 최소 신장 트리에 삽입한다. (삽입 시 사이클이 형성되지 않도록 함)
- 3번 과정을 반복한 후 모든 정점이 최소 신장 트리에 연결되면 종료한다.
- 프림 알고리즘에서 중요한 것은 최소 가중치를 찾는 것이다.
- 최소 가중치를 빠르게 찾기 위해서 힙(Heap)을 사용한다.
- 최소 신장 트리에서 정점과 인접한 간선을 (가중치, 정점)으로 힙에 삽입하고, 힙에서 꺼낸 정점과 인접한 정점을 순회하면서 가중치가 최소인 정점을 다시 힙에 추가하면서 힙이 비어있을 때까지 반복한다. (이미 방문한 정점일 경우 트리에 추가x)
