의식이 흐르는대로 해보는 프로그래밍

목차 접근 최소 스패닝 트리를 구하고, 그 비용을 구하는 문제다. 문제 자체는 간단하기에 크루스칼 알고리즘을 이용해서, 쉽게 해결했다. 해결 각 별 사이들간의 거리를 미리 다 구해놓고, 연결된 별과 그 거리를 저장해준다. 또 거리를 기준으로 오름차순 정렬을 수행한 뒤, 크루스칼 알고리즘을 수행한다. 크루스칼 알고리즘은 Union-Find 알고리즘을 수행하는데, 해당 내용은 이전 아티클을 참고하자. 2023.12.21 - [알고리즘(Algorithm)] - [BOJ] 1197번 : 최소 스패닝 트리(Kruskal) 코드 n = int(input()) coords = [] edges = [] for _ in range(n): a, b = map(float, input().split()) coords.appe..

접근 연결된 그래프를 분할하고,그 가중치 합의 최솟값을 구해내는 문제다. 보자마자 당연히 먼저 든 생각은 다익스트라를 떠올렸지만, 그럼 마을을 분할하는 과정을 접근하기 쉽지않다. 그 다음에 든 생각은 저번에 풀었던 2023.12.21 - [알고리즘(Algorithm)] - [BOJ] 1197번 : 최소 스패닝 트리(Kruskal) 이 문제의 알고리즘인 크루스칼 알고리즘이 떠올랐다. 최소 스패닝 트리는 모든 노드를 연결하는 엣지들의 최소 가중치를 찾는 문제다. 그럼 모든 노드를 연결짓는 최소 가중치를 찾고, 나머지 하나 가장 큰 가중치의 엣지를 제거하면 되겠네? 라는 흐름으로 이어졌다. 해결 위에 언급했던대로, 크루스칼 알고리즘을 사용하여 쉽게 해결했다. 근데 처음 과정은 가장 큰 가중치 하나를 찾고, M..