[백준] 1647 - 도시 분할 계획

1. 문제

1647번: 도시 분할 계획

2. 개요

N개의 집과 M개의 유지비가 드는 도로가 있는 마을이 있다.

이 마을을 도로들을 없애 두 개의 마을로 분할하려고 한다. 마을 안의 모든 집은 연결되어야 하고 집이 하나는 있어야 한다.

이렇게 마을을 두 개로 분할할 때, 두 마을의 도로의 유지비의 최솟값을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

모든 마을을 잇는 최소비용의 그래프를 구한 뒤, 그 그래프 내의 최대비용의 간선을 지우면 된다.

따라서 최소 스패닝 트리를 구하는 알고리즘을 이용하면 된다.

최소 힙 또는 우선순위 큐에 비용이 0인 임의의 정점 하나를 넣고 시작한다.

힙에서 빼낸 정점이 이미 방문한 곳이라면 힙에서 빼내는 작업으로 돌아가고,

아니라면 이 정점을 방문처리하고, 총 비용에 더하고, 집 방문 카운트를 1늘려준다.

이 집까지 오는 도로의 비용이 지금까지의 최대도로비용보다 크다면 이를 갱신해준다.

다음으로 이 집에서 갈 수 있는 집, 도로의 비용을 모두 힙에 넣는다.

이를 N-1개의 집을 선택할 때 까지 반복한다.

반복문을 탈출했다면, 총 비용에서 최대도로비용을 뺀 값을 출력한다.

3-2. Python

import sys
import heapq

N, M = map(int, sys.stdin.readline().split())

visited = [False for i in range(N+1)]
graph = [[] for i in range(N+1)]
total = 0
maxcost = 0

for i in range(M):
    a, b, c = map(int, sys.stdin.readline().split())

    graph[a].append([b, c])
    graph[b].append([a, c])

q = [(0, 1)]
cnt = 0

while cnt <= N-1:
    nowcost, nowloc = heapq.heappop(q)

    if visited[nowloc]:
        continue

    total += nowcost
    visited[nowloc] = True
    cnt += 1

    if maxcost < nowcost:
        maxcost = nowcost

    for nextloc, nextcost in graph[nowloc]:
        if visited[nextloc]:
            continue

        heapq.heappush(q, (nextcost, nextloc))

print(total - maxcost)

3-3. C#

namespace boj_1647
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();
            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);

            int total = 0;
            int maxcost = 0;

            List<List<int[]>> graph = new List<List<int[]>>();

            for (int i = 0; i < N + 1; i++)
            {
                graph.Add(new List<int[]>());
            }

            bool[] visited = new bool[N + 1];

            for (int i = 0; i < M; i++)
            {
                string[] info = sr.ReadLine().Split();
                int a = int.Parse(info[0]);
                int b = int.Parse(info[1]);
                int c = int.Parse(info[2]);

                graph[a].Add(new int[] { b, c });
                graph[b].Add(new int[] { a, c });
            }

            int cnt = 0;

            PriorityQueue<int[], int> q = new PriorityQueue<int[], int>();
            q.Enqueue(new int[] { 0, 1 }, 0);

            while (cnt <= N - 1)
            {
                int[] now = q.Dequeue();
                int nowcost = now[0];
                int nowloc = now[1];

                if (visited[nowloc])
                    continue;

                visited[nowloc] = true;
                total += nowcost;
                cnt++;

                if (nowcost > maxcost)
                    maxcost = nowcost;

                foreach (int[] next in graph[nowloc])
                {
                    int nextloc = next[0];
                    int nextcost = next[1];

                    if (visited[nextloc])
                        continue;

                    q.Enqueue(new int[] {nextcost, nextloc}, nextcost);
                }
            }

            sw.WriteLine(total - maxcost);
            sw.Close();
        }
    }
}