[백준] 1922번 네트워크 연결

문제

https://www.acmicpc.net/problem/1922

고민

모든 컴퓨터를 연결하되 최소한의 선을 연결하고 싶다. => 최소 스패닝 트리

 

최소 스패닝 트리는 모든 정점을 연결하지만, 사이클이 없습니다. 모든 정점은 하나의 간선만 연결되어야 한다는 것입니다 후후,, 이게 무슨 말이냐면

차이가 보이시나요? 위 그래프를 보면 모든 노드가 하나의 간선으로만 연결되어 있습니다. 이는 '순환하지 않는다'라고 합니다. 아래 그래프를 보면 A와 B가 2개의 간선으로 연결되어 있습니다. 이러한 모습을 보고 '순환한다'라고 합니다.

 

자세하게 설명하는 이유는 제가 줄글로 순환/비순환을 보았을때 무슨 말인지 몰랐거든요^!^

 

그렇다면 순환하지 않으려면 어떻게 해야할까요? 바로 '방문처리'입니다.

방문처리를 한다면 중복으로 노드를 방문하지 않으니 순환하지 않는 트리를 만들 수 있습니다!

 

또한 최소스패닝 문제를 풀 때는 두가지 알고리즘을 고민 할 수 있습니다.

1. 프림

2. 크루스칼

 

저는 프림을 활용해서 문제를 풀었습니다.

 

프림은 현재 선택된 노드와 연결된 다음 노드 중 비용이 가장 적은 노드를 선택해서 연결하는 방식입니다.

예를들어,, 1번 노드에 2번과 3번이 연결되어 있고 각각 비용이 4와 7이라고 합시다. 여기서 비용이 제일 저렴한 것은 4이므로 2번 노드를 방문. 2번 노드를 방문했더니 5과 8에 연결되어 있고.... 이걸 계속 반복하는 것입니다. 그러다 visited에 모두 방문처리가 되었으면 트리가 모두 연결되었다 간주하는 것이죵

코드

using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.InteropServices;
using System.Text;
using System.Threading.Tasks;

namespace MST
{
    class Computer
    {
        public int nextCom;
        public int cost;

        // 생성자
        public Computer(int nextCom, int cost)
        {
            this.nextCom = nextCom;
            this.cost = cost;
        }
    }

    internal class 네트워크_연결
    {
        static int comCount, lineCount;
        static List<Computer>[] comes; // 인접 리스트
        static bool[] visited;
        static int minimumCost = 0;
        static void Main(string[] args)
        {
            comCount = int.Parse(Console.ReadLine()); // 컴퓨터
            lineCount = int.Parse(Console.ReadLine()); // 연결 가능한 선의 수

            comes = new List<Computer>[comCount+1];
            visited = new bool[comCount+1];

            for (int i = 1; i <= comCount; i++)
            {
                comes[i] = new List<Computer>();
            }

            for (int i = 0; i < lineCount; i++)
            {
                int[] input = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
                int currentCom = input[0];
                int nextcom = input[1];
                int cost = input[2];

                comes[currentCom].Add(new Computer(nextcom, cost));
                comes[nextcom].Add(new Computer(currentCom,cost));
            }

            Prim(1);
            Console.WriteLine(minimumCost);
        }

        static void Prim(int start)
        {
            PriorityQueue<Computer, int> pq = new PriorityQueue<Computer, int>();

            visited[start] = true;

            foreach(var v in comes[start])
            {
                pq.Enqueue(v, v.cost); // 첫번째 컴퓨터와 연결된 모든 컴퓨터를 담음
            }

            while(pq.Count > 0)
            {
                var temp = pq.Dequeue();

                if (visited[temp.nextCom] == false) // 다음 컴퓨터를 방문한 전적이 없으면
                {
                    visited[temp.nextCom] = true;
                    minimumCost += temp.cost;

                    foreach(var v in comes[temp.nextCom])
                    {
                        if (visited[v.nextCom] == false)
                        {
                            pq.Enqueue(v, v.cost);
                        }
                    }
                }
            }
        }
    }
}

정답은 23인데 제 프로그램은 26이 나오길래 알쏭쏭했습니다. 디버깅을 열심히 해본 결과 그래프를 그릴 때 쌍방으로 연결을 안해줬더라고요.. 그래서 더 적은 수가 있음에도 알리 없으니 계속 이상한 방향으로 갔던 것입니다... 다른 분들은 까먹지 말길..

 

**문제에 따라서 단방향, 양방향 연결을 해줘야 하는 경우가 다르지 이점에 주의해서 문제를 풀어봅시다!