크루스칼 알고리즘

https://www.acmicpc.net/problem/1197 문제 분석 첫 번째 단계 (문제 요약 및 조건 파악) 그래프가 주어졌을 때, 그 그래프의 최소 신장 트리 를 구하는 프로그램을 작성하시오. 최소 신장 트리(MST)는 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. - 입력 첫째 줄에는 정점의 개수 v(1

크루스칼 알고리즘 (Kruskal Algorithm) 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 '최소 신장 트리 알고리즘' 이라고 하는데, 대표적인 최소 신장 트리 알고리즘으로는 크루스칼 알고리즘 이 있다. 크루스칼 알고리즘 을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있다. 크루스칼 알고리즘은 대표적인 최소 신장 트리 알고리즘 이다. 그리디 알고리즘으로 분류된다. 그렇다면, 신장 트리란 무엇인가? 신장 트리 란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. → 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는 다는 조건은 트리 의 성립 조건이기도 함. 신장 트리는 알겠고.. 그러면 최소 신장 ..

도시 분할 계획 동물원에서 막 탈출한 원숭이 한 마리가 세상 구경을 하고 있다. 어느 날 원숭이는 '평화로운 마을'에 잠시 머물렀는데 마침 마을 사람들은 도로 공사 문제로 머리를 맞대고 회의 중이었다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 길마다 길을 유지하는데 드는 유지비가 있다. 마을의 이장은 마을을 2개의 분리된 마을로 분할할 계획을 세우고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다. 그렇게..

이미 배운 내용을 훑어보자 지금까지 코딩 테스트에서 출제 비중이 높은 알고리즘 유형들을 다루어보았다. 이번 장에서는 지금까지 다루지 않았던 그래프 알고리즘을 추가로 다룰 것이다. 이전 5장 'DFS/BFS'와 9장 '최단 경로'에서 다룬 내용은 모두 그래프 알고리즘의 한 유형으로 볼 수 있다. 이외에도 그래프 알고리즘은 굉장히 다양한데, 코딩 테스트에서 출제 비중이 낮은 편이지만 꼭 제대로 알아야 하는 알고리즘이다. 여기서 다루는 개념들을 바르게 이해할 수 있다면 코딩 테스트에서 만나게 될 다양한 응용문제들도 해결할 수 있을 것이다. 10장에서 다룰 알고리즘은 앞서 배운 내용에 기반하는데, 예를 들어 크루스칼 알고리즘(Kruskal Algorithms)은 그리디 알고리즘으로 분류되며, 위상 정렬 알고리즘..