목록1647 (1)

계단을 오르듯이

[JAVA] 1647. 도시 분할 계획

도시를 분할 때 2개의 도시를 만들고 연결하는 최소의 유지비용을 구하는 문제이다. 최소의 거리값을 구하는 크루스칼 알고리즘을 사용하였다. 우선 최소의 비용을 구하기 위해 가장 작은 비용으로 모든 집을 연결해야했고, 그 중 최소의 연결 비용을 위해 가장 큰 값의 연결 유지비용을 제외해 마을을 나누어야 한다. 문제에서 2개의 도시는 최소 1개 이상의 집이 존재하여야 한다고 하였으므로 각 마을의 집을 모두 최소의 비용으로 연결한 후 마지막 가장 큰 비용으로 연결되어지는 하나의 집을 제외하여 다른 마을로 만들면 그 방식이 가장 최소의 비용으로 모든 집을 연결하고, 가장 큰 비용이 드는 집의 연결을 제거해 하나의 마을로 만드는 것이 최소의 유지비용이 될 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 1..
알고리즘/백준_JAVA 2022. 2. 2. 09:24
이전 Prev 1 Next 다음