[필수 알고리즘] MST

개념

- Minimum Spanning Tree

- Spanning Tree : 모든 노드가 연결된 트리

- MST : 최소 비용으로 모든 노드가 연결된 트리

 

MST 푸는 방법

- Kruskal or Prim

- Kruskal : 전체 간선 중 작은 것부터 연결

- Prim : 현재 연결된 트리에 이어진 간선중 가장 작은 것을 추가

 

MST 팁

- 모든 노드가 연결되도록 한다거나, 이미 연결된 노드를 최소의 비용으로 줄이는 것 MST 사용!

 

heap 사용

- 최대값, 최소값을 빠르게 계산하기 위한 자료구조

- 이진 트리 구조

- 처음에 저장할때부터 최대 or 최소값 결정

 

핵심코드

heap = [[0,1]] -> 앞자리 0은 비용, 뒷자리 1은 노드 번호

PriorityQueue<int[], int> heap = new PriorityQueue<int[], int>();

// 시작 노드를 우선순위 큐에 추가 (비용 0, 노드 번호 1)
heap.Enqueue(new int[] { 0, 1 }, 0);

// 힙을 이용한 프림 알고리즘의 주요 로직
while (heap.Count > 0)
{
    // 가장 비용  가 작은 간선 정보 추출
    int[] current = heap.Dequeue();
    int w = current[0];          // 비용  
    int each_node = current[1];  // 노드 번호
    
    if (chk[each_node] == false)
    {
        // 아직 방문하지 않은 노드라면
        chk[each_node] = true;   // 방문 처리
        rs += w;                 // 비용   누적
        
        // 인접한 간선들을 우선순위 큐에 추가
        foreach (var next_edge in edge[each_node])
        {
            if (chk[next_edge[1]] == false)  // 아직 방문하지 않은 노드라면
            {
                // 우선순위 큐에 추가 (비용  를 우선순위로 사용)
                heap.Enqueue(next_edge, next_edge[0]);
            }
        }
    }
}

 

아이디어

- 최소스패닝 트리 기본문제(외우기)

- 간선을 인접 리스트 형태로 저장

- 시작점부터 힙에 넣기

- 힙이 비어질때까지 실행 

 

시간복잡도

- Edge 리스트에 저장 : O(E)

- Heap안 모든 Edge에 연결된 간선 확인 : O(E + E)

- 모든 간선 힙에 삽입 : O(ElgE)

- O(E + 2 E + ElgE)  = O(3E + ElgE) = O(E(3+lgE)) = O(ElgE)

 

자료구조

- Edge 저장하는 (int,int)[]

-> 비용 최대

-> 정점 번호 최대

- 정점 방문 : bool[]

- MST 비용 : int

 

문제풀이

- 백준 1197

 

1.

class num_1197
{
    static void Main(string[] args)
    {
        var sr = new StreamReader(Console.OpenStandardInput());
        var sw = new StreamWriter(Console.OpenStandardOutput());

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

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

        var edge = new List<List<int[]>>();
        for (int i = 0; i <= V; i++)
        {
            edge.Add(new List<int[]>());
        }

        for (int i = 0; i < E; i++)
        {
            string[] input_ = sr.ReadLine().Split();
            int a = int.Parse(input_[0]);//노드번호
            int b = int.Parse(input_[1]);//노드번호
            int c = int.Parse(input_[2]);//비용

            edge[a].Add(new int[] { c, b });
            //양방향이기 때문에 a,b 두개를 넣어야함
            edge[b].Add(new int[] { c, a });
        }
    }
}

- bool[] chk = new bool[V + 1]; 에서 V+1인 이유는 문제에서 V가 1부터 시작이기 때문 

- for (int i = 0; i <= V; i++) 또한 마찬가지

- "var edge = new List<List<int[]>>();"로 저장하는 이유는 노드별로 각 간선정보를 저장하기 위함 입니다.

 

2.

PriorityQueue<int[], int> heap = new PriorityQueue<int[], int>();

// 시작 노드를 우선순위 큐에 추가 (비용 0, 노드 번호 1)
heap.Enqueue(new int[] { 0, 1 }, 0);

int result = 0;
while (heap.Count > 0)
{
    //값 뽑아서 체크
    var data = heap.Dequeue();
    int w = data[0];
    int each_node = data[1];

    //방문했는지 체크
    if (chk[each_node])
    {
        continue;
    }

    //방문표시
    chk[each_node] = true;

    //비용 추가
    result += w;

    //each_node의 간선들 체크
    foreach (var item in edge[each_node])
    {
        //노드에 방문 했는지 체크
        if (chk[item[1]])
        {
            continue;
        }

        //간선 정보(비용, 다음 노드) 우선순위 큐에 추가
        heap.Enqueue(item, item[0]);
    }
}

sw.WriteLine(result);
sw.Flush();
sw.Close();
sr.Close();

- 우선순위 큐인 PriorityQuene로 변수를 만들어주고 시작값 추가

- heap 변수 값을 돌며 비용을 추가해 모든 간선이 연결된 최소 비용 출력

 

최종코드

/*
1. 아이디어
- MST 기본문제 외워서 풀 것
- 간선을 인접리스트에 집어넣기
- 힙에 시작점 넣기
- 힙이 비어질때까지 작업 반복
-> 힙 최소값 꺼내서, 노드 방문 여부 확인
-> 방문 안했다면 방문표시 및 비용 추가, 연결된 간선 힙에 넣기기

2. 시간복잡도
- MST : O(ElgE)

3. 자료구조
- 간선 저장되는 인접리스트 : (비용, 노드번호)
- 힙 : (비용, 노드번호)
- 방문 여부 : bool[]
- MST 결과값 : int
*/

class num_1197
{
    static void Main(string[] args)
    {
        var sr = new StreamReader(Console.OpenStandardInput());
        var sw = new StreamWriter(Console.OpenStandardOutput());

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

        //1부터 시작이라 +1
        bool[] chk = new bool[V + 1];

        //인접리스트 생성 <= 이유는 1부터 시작이기 때문에 <=로 진행
        var edge = new List<List<int[]>>();
        for (int i = 0; i <= V; i++)
        {
            edge.Add(new List<int[]>());
        }

        for (int i = 0; i < E; i++)
        {
            string[] input_ = sr.ReadLine().Split();
            int a = int.Parse(input_[0]);//노드번호
            int b = int.Parse(input_[1]);//노드번호
            int c = int.Parse(input_[2]);//비용

            edge[a].Add(new int[] { c, b });
            //양방향이기 때문에 a,b 두개를 넣어야함
            edge[b].Add(new int[] { c, a });
        }

        PriorityQueue<int[], int> heap = new PriorityQueue<int[], int>();

        // 시작 노드를 우선순위 큐에 추가 (비용 0, 노드 번호 1)
        heap.Enqueue(new int[] { 0, 1 }, 0);

        int result = 0;
        while (heap.Count > 0)
        {
            //값 뽑아서 체크
            var data = heap.Dequeue();
            int w = data[0];
            int each_node = data[1];

            //방문했는지 체크
            if (chk[each_node])
            {
                continue;
            }

            //방문표시
            chk[each_node] = true;

            //비용 추가
            result += w;

            //each_node의 간선들 체크
            foreach (var item in edge[each_node])
            {
                //노드에 방문 했는지 체크
                if (chk[item[1]])
                {
                    continue;
                }

                //간선 정보(비용, 다음 노드) 우선순위 큐에 추가
                heap.Enqueue(item, item[0]);
            }
        }

        sw.WriteLine(result);
        sw.Flush();
        sw.Close();
        sr.Close();
    }
}

 

참고영상

- 바로가기