2023.05.17[최소 신장 트리]

일상/Today I Learned

YJzero 2023. 5. 17. 11:25

: 그래프 내의 모든 정점을 포함하는 트리

=> 모든 정점들이 연결되어 있고 n개의 정점을 갖는 경우 (n-1)개의 간선으로 연결된다.

: Spanning Tree 중 사이클을 만들지 않고 간선들의 가중치 합이 최소인 트리

=> 각 간선의 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것. 단순히 가장 적은 간선을 사용한다고 해서 최소 비용이 얻어지는 것이 아님!

ex) 통신망, 도로망, 유통망 등... 어떤 그래프 형태에서 길이, 구축 비용, 전송 시간 등을 최소로 구하는 경우

MST 구현 방법

1. 크루스칼 알고리즘

: 그리디(탐욕법) 알고리즘 중 하나

-> 그래프의 모든 정점을 사이클 없이 최소 비용으로 연결하는 최적 해답을 구하는 것

사이클을 생성하는지 판단하는 것이 Union-find 자료구조이다.

* Union-find란?

: 서로소 집합을 표현하는 자료구조

-> 서로 다른 두 집합을 병합하는 union 연산 + 집합 연소가 어떤 집합에 속해있는지 찾는 find 연산

- union-find 에서는 각 노드가 연결된 최소 노드를 root 노드로 갖게 된다.

따라서 각 노드를 비교하면서 작은 값을 부모 노드로 저장한다. 부모 노드를 기준으로 union 연산에 의해 합쳐지게 되는 것! 만약 이미 부모 노드가 같다면? 연결된 상태이기 때문에 제외하고 다음으로 넘어가면 된다.

2. Prim MST 알고리즘

: 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장 해나가는 방법

풀이완

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

1197번: 최소 스패닝 트리

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이

www.acmicpc.net

1922번: 네트워크 연결

이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다.

www.acmicpc.net

참고

이게 무슨 알고리즘인가.. 싶었지만 개념을 알고보니 그렇게 어려운 개념은 아니었다! 관련 문제를 풀어보면서 익숙하게 사용할 수 있게 되는 것이 관건일 것 같다. 오늘 관련 문제 좀 더 풀어봐야지!