(C#) 섬 연결하기

코딩테스트 연습 - 섬 연결하기 | 프로그래머스 스쿨

프로그래머스

 

모든 정점을 포함하는 최단 경로를 구하는 문제 -> 크루스칼 알고리즘을 적용하기로 했다

사실 처음에는 이전에 다른 문제를 풀 때 사용했던 플루이드-워셜 알고리즘을 적용하려고 했는데, 잘 안됐다

 

크루스칼 알고리즘은 최소신장트리를 구하는 알고리즘이다

최소신장트리는 모든 정점을 포함하고 순환 구조가 없는 트리들 중에 가중치 합이 최소인 트리를 말한다

 

아무튼 크루스칼 알고리즘을 적용하면 모든 섬을 연결하는 경로 중 최단 경로를 구할 수 있다

 

1. 간선들의 가중치를 오름차순으로 정렬한다

2. 가장 가중치가 작은 간선을 연결한다

3. 정점을 연결한 뒤에 순환 구조가 있는지 확인한다

4. 2~3의 과정을 반복한다. 연결된 간선의 갯수가 정점의 수 - 1이 되면 종료한다

 

문제는 순환구조를 확인하는 부분이다.

 

여기서 크루스칼 알고리즘은 union이라는 자료구조를 활용한다

union은 각 정점들의 루트 정점을 기록하는 배열이다

 

union의 초기값은 자기자신으로 한다. 모든 정점의 루트가 자기자신이기 때문이다.

0	1	2	3
0	1	2	3

 예제에서 0번 정점과 1번 정점을 연결한다.

 두 정점의 루트가 서로 다르므로 순환구조가 없다고 판단할 수 있다.

 두 정점이 이제 같은 트리에 있으므로 1번 정점의 루트를 갱신한다

0	1	2	3
0	0	2	3

 

 이런 방식으로 진행하면 된다

 

코드

using System;

public class Solution {
    int[] vertice;
    int find(int x)
    {
        if (vertice[x] != x)
            vertice[x] = find(vertice[x]);
        return vertice[x];
    }
    void union(int x, int y)
    {
        int _x = find(x);
        int _y = find(y);
        if (_x != _y)
            vertice[_y] = _x;
    }

    public int solution(int n, int[,] costs)
    {
        int answer = 0;
        int count = 0;
        vertice = new int[n];
        int[][] ncosts = new int[costs.GetLength(0)][];
        for (var i = 0; i < costs.GetLength(0); i++)
        {
            ncosts[i] = new int[] { costs[i, 0], costs[i, 1], costs[i, 2] };
        }
        Array.Sort(ncosts, (x, y) =>
        {
            return x[2] - y[2];
        });

        for (var i = 0; i < n; i++)
        {
            vertice[i] = i;
        }

        for (var i = 0; i < ncosts.Length; i++)
        {
            if (find(ncosts[i][0]) == find(ncosts[i][1])) continue;
            union(ncosts[i][0], ncosts[i][1]);

            answer += ncosts[i][2];
            count++;
            if (count == n - 1) break;
        }
        return answer;
    }
}

 

결과