알고리즘 기본기 다지기12. 그래프 알고리즘(가중그래프, 최소신장트리,최단경로, 탐욕법)

컴퓨터/data science

알고리즘 기본기 다지기12. 그래프 알고리즘(가중그래프, 최소신장트리,최단경로, 탐욕법)

김크리 2021. 8. 26. 21:44

가중 그래프(Weighted Graph)

정점과 정점 사이를 잇는 간선에 대해 가중치가 주어진 그래프를 말한다. 가중 그래프중 방향 그래프를 네트워크(Network)라고 한다. 가중치는 양수와 음수 모두 가질 수 있으며, 대표적인 최단 경로 문제에서는 가중치의 합이 최소가 되는 경로를 구하는 문제가 출제된다. 네비게이션의 경우 자동차의 최단 경로를 안내하는데 도로를 가중 그래프로 모델링하고 최소 비용 경로를 찾는 것이다.

최소신장트리

그래프의 모든 정점을 지나는 트리 중에서 간선 비용의 합이 최소인 트리를 최소 비용 신장 트리라고 한다.
이를 이용하여 최소의 비용으로 네트워크를 구성하는 문제 등을 해결할 수 있다.

Kruskal 알고리즘

최소 비용 신장 트리를 구하기 위한 대표적인 알고리즘이다.
우선순위 탐색과 집합의 개념을 이용하여 단순한 알고리즘으로 정리한다.

간선의 가중치를 오름차순으로 정렬
가중치가 가장 작은 간선 선택
그 다음 가중치가 가장 작은 간선과 해당 간선의 노드가 연결되어있는지 확인하고 연결되지 않았다면 Skip, 연결되었다면 가중치 값 저장
위의 내용 반복

Prim-Jarnik 알고리즘

단순 연결 무방향 가죽그래프에 대한 최소신장 트리를 계산한다.

시작 정점을 선택한다. 선택한 정점은 해당 그래프의 루트(root)가 된다.
루트로부터 연결된 다른 정점을 찾아나가며 그래프를 키워나간다.
시작 정점의 탐색이 끝나면, 시작 정점의 자식으로 부터 탐색을 하며 최소 가중치를 찾는다.
위의 탐색이 끝나면 해당 정점으로 새로운 경로나 갱신할 수 있는 것을 탐색한다.
3과 4를 반복하면 최소 가중치를 찾는다.

최단경로(Shortest path problem)

가중 그래프와 두개의 정점이 주어졌을때 정점 사이의 무게ㅢ 합이 최소인 경로를 구하는 문제를 말한다.

Dijkstra 알고리즘

Dijkstra(다익스트라) 알고리즘은 대표적인 최단경로 알고리즘이다. 간단한 논리 전재로 최단 경로 알고리즘을 풀 수 있는 알고리즘이다. 음의 무게를 가진 간선이 없는 그래프에 적용된다. 가장 중요한 특징은 탐욕법에 기초한다는 점이다.

출발 정점으로 부터 다른 모든 정점까지의 거리를 계산한다.
위에 속하지 않는 정점 중 가장 가중치가 낮은 정점을 다음 출발 정점으로 선택한다.
1,2를 반복한다.

Bellman-Ford 알고리즘

음의 무게를 가진 간선이 있더라도 정확히 작동한다. 왜냐하면 벨먼 포드 알고리즘은 모든 간석을 확인하기 때문이다.

DAG 최단 경로 알고리즘

방향 비싸이클 그래프(DAG)의 경우 Dijkstra나 Bellman-Ford알고리즘 보다 최단 경로를 구하는 알고리즘이 있다. 위상 순서를 이용하여 DAG에 음의 무게를 가진 간선이 있더라도 정확히 작동한다.

그래프의 위상 순서를 구한다.
각 정점의 거리를 무한대로 초기화 한 후 출발 정점의 거리를 0으로 저장한다
위를 반복하며 위상 순서 상의 정점을 차례대로 접근하여 정점의 진출 부착간선들을 완화한다.

연습문제

백준

1197(최소 스패닝 트리) 1922(네트워크 연결) 1647(도시 분할 계획) 2887(행성터널) 4386(별자리 만들기)

1753(최단경로) 1916(최소비용구하기) 1261(알고스팟) 1238(파티)

탐욕법(Greedy)

탐욕법, 그리디 알고리즘은 동적 프로그래밍(DP, Dynamic Programming) 사용 시 너무 많은 일을 한다는 것에서 고안된 알고리즘이다. 동적 프로그래밍을 대체하는 것은 아니고 상호보완하는 개념이다. 탐욕법이라 불리는 이유는 현재 단계에서 가장 최선의 선택을 하는 기법이다.