프로그래머스 - 지형 이동 (C#) [Lv. 4]

프로그래머스

N * N 크기의 정사각 격자 형태의 지형이 있습니다. 각 격자 칸의 높이를 배열로 입력 받고, 사다리 없이 이동할 수 있는 높이를 입력 받습니다. 우리는 모든 지형을 연결하기 위해 사다리를 사용해야 합니다. 이 때, 사다리를 사용하여 지형을 연결할 수 있는 최소 비용을 구해주세요.

(사다리의 비용은 두 격자 칸의 높이 차이가 됩니다.)

 

 

이 문제는 Union - Find 알고리즘과 크루스칼 알고리즘을 제대로 활용할 수 있는지 테스트 하는 문제입니다.

Union - Find에 대해 잘 모른다면 아래 링크를 참고해주세요.

크루스칼 알고리즘과 유니온 파인드

 

풀이 방법

(Union-Find)

BFS를 통해, 갈 수 있는 격자를 Union - Find 알고리즘을 이용하여 하나로 합쳐줍니다. 

이후에 갈 수 없는 노드(사다리가 필요)의 경우 List에 따로 저장하여 해당 List를 이용하여 최종 비용을 계산하게 됩니다.

 

List를 순회하여 이후에 합쳐진 격자들은 제외하고 사다리가 꼭 필요한 경우의 중복을 없애 줍니다.

(0번 -> 2번 (비용 3)), (0번 -> 2번 (비용 5))가 List에 담겨있는 경우 최소 비용만 남기고 나머지는 지웁니다.

 

(크루스칼 알고리즘)

이렇게 남은 비용들을 이용하여 모든 격자를 합치는 최소 비용을 구해줍니다.

비용을 기준으로 List를 오름차순 정렬해주고, 비용이 낮은 순서부터 격자를 합쳐줍니다. 

모든 격자가 합쳐진 상태라면 최종 비용을 반환합니다. 

 

 

자세한 설명

1. 갈 수 없는 지형을 List에 담기

BFS를 이용하여 모드 격자에 대한 탐색을 시도합니다.

이 때, 갈 수 있는 지형은 Union - Find를 이용하여 하나로 합쳐줍니다.

그리고 갈 수 없는 지형은 List에 출발지, 도착지, 비용을 저장해줍니다.

// 비용을 계산하고 사다리 없이 갈 수 있는 높이가 아니라면
// List에 해당 정보를 저장
int cost = Math.Abs(land[cy, cx] - land[ny, nx]);
if (cost > h){
    costs.Add((cIdx, nIdx, cost)); // 출발지, 도착지, 비용
    continue;
}

// 사다리 없이 갈 수 있다면, 두 격자를 하나로 합쳐주기
Union(parents, cIdx, nIdx);
q.Enqueue((ny, nx));

 

 

2. 갈 수 없는 지형 List를 순회하여 지역에서 지역으로 가는 최소 비용 구하기

사다리가 필요한 모든 경우를 List에 넣어주었기 때문에,

중복된 경우를 없애줄 필요가 있습니다. 이것을 Dictionary를 활용하여 빠르게 해결해줍니다.

Dictionary<(int, int), int> dic = new Dictionary<(int, int), int>();

foreach (var tpl in costs)
{
	// 출발지, 도착지, 비용
    var (stt, dst, cost) = tpl;
    ...
    ...
    ...
	// 출발지 -> 도착지까지의 비용이 이미 추가되어 있다면 최소 비용으로 업데이트
    if (dic.ContainsKey((stt, dst)))
        dic[(stt, dst)] = Math.Min(dic[(stt, dst)], cost);
    else
        dic[(stt, dst)] = cost;
}

 

 

3. 사다리가 필요한 모든 경우를 Dictionary에 중복 없이 넣어준 후, List에 넣고 비용을 기준으로 정렬합니다.

costs.Sort((a, b) => a.Item3.CompareTo(b.Item3));

 

 

4. 비용을 기준으로 오름차순 정렬된 리스트를 순회하여 노드를 함치고 비용을 더해줍니다.

int answer = 0;
foreach (var c in costs)
{
    var (stt, dst, cost) = c;
    stt = Find(parents, stt);
    dst = Find(parents, dst);
    
    // 이미 합쳐진 격자라면 건너뛰기
    if (stt == dst)
        continue;

	// 두 격자를 합쳐주고 answer에 비용 추가
    Union(parents, stt, dst);
    answer += cost;
}

 

 

 

 

 

---

정답 코드

Union - Find 함수

int IDX(int y, int x, int n){ return y * n + x;}
(int, int) IDX(int idx, int n) { return (idx / n, idx % n);}


int Find(int[] parents, int a)
{
    if (parents[a] == a)
        return a;

    return parents[a] = Find(parents, parents[a]);
}

void Union(int[] parents, int a, int b)
{
    a = Find(parents, a);
    b = Find(parents, b);

    if (a <= b)
        parents[b] = a;
    else
        parents[a] = b;
}

 

 

BFS

int[] dy = {0, 0, 1, -1};
int[] dx = {1, -1, 0, 0};

void BFS(int[,] land, int[] parents, 
         int h, int y, int x, ref List<(int, int, int)> costs)
{
    int n = land.GetLength(0);

    Queue<(int, int)> q = new Queue<(int, int)>();
    q.Enqueue((y, x));
    while (q.Count > 0)
    {
        var (cy, cx) = q.Dequeue();

        for (int i = 0; i < 4; i++)
        {
            var (ny, nx) = (cy + dy[i], cx + dx[i]);

            // ny, nx가 land 안에 있지 않다면 건너 뛰기
            if (ny < 0 || nx < 0 || 
                ny >= land.GetLength(0) || nx >= land.GetLength(1))
                continue;

            int cIdx = IDX(cy, cx, n);
            int nIdx = IDX(ny, nx, n);

            // 이미 연결되어 있다면 건너 뛰기
            if (Find(parents, cIdx) == Find(parents, nIdx))
                continue;


            // 높이가 너무 높으면 건너 뛰기
            int cost = Math.Abs(land[cy, cx] - land[ny, nx]);
            if (cost > h){
                costs.Add((cIdx, nIdx, cost));
                continue;
            }

            Union(parents, cIdx, nIdx);
            q.Enqueue((ny, nx));
        }
    }
}

 

 

Solution

public int solution(int[,] land, int height) {

    int n = land.GetLength(0);
    int m = land.GetLength(1);

    Dictionary<(int, int), int> dic = new Dictionary<(int, int), int>();
    List<(int, int, int)> costs = new List<(int, int, int)>();

    int[] parents = new int[90001];        
    for (int i = 0; i < n*m; i++)
        parents[i] = i;   

    for (int i = 0; i < land.GetLength(0); i++)
        for (int j = 0; j < land.GetLength(1); j++)
            BFS(land, parents, height, i, j, ref costs);

    foreach (var tpl in costs)
    {
        var (stt, dst, cost) = tpl;
        stt = Find(parents, stt);
        dst = Find(parents, dst);

        if (stt == dst)
            continue;

        if (stt > dst)
        {
            int tmp = stt;
            stt = dst;
            dst = tmp;
        }

        if (dic.ContainsKey((stt, dst)))
            dic[(stt, dst)] = Math.Min(dic[(stt, dst)], cost);
        else
            dic[(stt, dst)] = cost;
    }

    costs.Clear();
    foreach (var d in dic)
    {
        var (stt, dst) = d.Key;
        costs.Add((stt, dst, d.Value));
    }

    costs.Sort((a, b) => a.Item3.CompareTo(b.Item3));

    int answer = 0;
    foreach (var c in costs)
    {
        var (stt, dst, cost) = c;
        stt = Find(parents, stt);
        dst = Find(parents, dst);
        if (stt == dst)
            continue;

        Union(parents, stt, dst);
        answer += cost;
    }

    return answer;
}