백준 16471 백준 1647번: 도시 분할 계획 (C++) 문제링크 https://www.acmicpc.net/problem/16398 풀이방법 해당 문제는 최소 신장 트리를 구하는 알고리즘을 사용하여 해결할 수 있다. 최소 신장 트리를 찾는 알고리즘에는 두 가지가 있다. 하나는 크루스칼 알고리즘 나머지 하나는 프림 알고리즘이다. 이 중 프림 알고리즘을 사용하여 해당 문제를 해결하였다. 최소 신장 트리를 찾는 알고리즘에 대한 개념이 없다면 아래 영상을 참고하자. https://www.youtube.com/watch?v=4wA3bncb64E&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=28 우선 마을 하나하나를 그래프의 노드라고 생각한다. 그 상태로 최소 신장 트리를 만든다. 그럼 모든 마을이 연결되어있고 가중치의 합이 최소인.. 2024. 2. 3. 이전 1 다음