[백준] 1197 - 최소 스패닝 트리

1. 문제

1197번: 최소 스패닝 트리

2. 개요

그래프가 주어졌을 때, 그래프의 최소 스패닝 트리를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

최소 스패닝 트리란, 그래프의 모든 정점을 연결하는 가중치가 최소인 트리이다.

최소 스패닝 트리를 구하는 알고리즘으로는 크루스칼 알고리즘과 프림 알고리즘이 있다.

여기서는 프림 알고리즘을 사용했다.

임의의 한 정점을 잡고 그 정점에서 이어진 가중치가 최소인 간선을 긋는다.

이후에는 트리에 포함된 정점에서 이어진 가중치가 최소인 간선을 찾아 계속 그어나가면 된다.

간선을 그을 때마다 답을 가중치만큼 늘려준다.

작업이 끝났다면 답을 출력한다.

3-2. Python

import sys
import heapq

answer = 0
V, E = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(V + 1)]
visited = [False for _ in range(V + 1)]

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

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

q = [[0, 1]]

while q:
    cost, now = heapq.heappop(q)

    if visited[now]:
        continue

    answer += cost
    visited[now] = True

    for nxt, nextcost in graph[now]:
        heapq.heappush(q, [nextcost, nxt])

print(answer)

3-3. C#

namespace boj_1197
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int answer = 0;
            string[] input = Console.ReadLine().Split();
            int V = int.Parse(input[0]);
            int E = int.Parse(input[1]);

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

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

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

            for (int i = 0; i < E; i++)
            {
                string[] info = Console.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 });
            }

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

            while (q.Count > 0)
            {
                int[] now = q.Dequeue();
                int nownum = now[1];
                int nowcost = now[0];

                if (visited[nownum])
                    continue;

                visited[nownum] = true;
                answer += nowcost;

                foreach (int[] nxts in graph[nownum])
                {
                    int nxtnum = nxts[0];
                    int nxtcost = nxts[1];
                    q.Enqueue(new int[] { nxtcost, nxtnum }, nxtcost);
                }
            }

            Console.WriteLine(answer);
        }
    }
}