(C#) 지형 이동

코딩테스트 연습 - 지형 이동 | 프로그래머스 스쿨

프로그래머스

 지형을 사다리 없이 이동할 수 있는 구역으로 나누고, 각 구역들에서 최소신장트리를 찾는다

 

 BFS를 통해 사다리 없이 이동할 수 있는 구역들로 나눈다.

 BFS는 많이 써봤으니까 그냥 하면 된다.

 visited[,] 라는 이름으로 2차원 배열을 만들어서 구역들을 표시했다.

 

 다음은 각 구역들에서 다른 구역으로 가는 간선을 만든다.

 예시의 그림에서라면 노란색 구역의 5에서 파란색 구역의 10으로 가는 사다리를 4개 놓을 수 있고, 파란색 구역에서 빨간색 구역으로 가는 사다리를 2개 놓을 수 있다.

 각 사다리에 대해서 (시작 구역, 도착 구역, 가중치)를 간선으로 기록한다.

 이를 그래프로 나타내면 위와 같을 것이다.

 

 마지막으로 주어진 그래프에서 최소신장트리를 구한다.

코드

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int solution(int[,] land, int height)
    {
        int answer = 0;
        int row = land.GetLength(0);
        int col = land.GetLength(1);
        int[,] visited = new int[row, col];
        int num = 1;
        int[] dx = { -1, 0, 1, 0 };
        int[] dy = { 0, -1, 0, 1 };

        // 사다리 없이 갈 수 있는 지형으로 묶기
        for (var i = 0; i < row; i++)
        {
            for (var j = 0; j < col; j++)
            {
                if (visited[i, j] == 0)
                {
                    Queue<(int x, int y)> que = new Queue<(int x, int y)>();
                    que.Enqueue((i, j));
                    visited[i, j] = num;
                    while (que.Count != 0)
                    {
                        var current = que.Dequeue();
                        for (var k = 0; k < 4; k++)
                        {
                            var _x = current.x + dx[k];
                            var _y = current.y + dy[k];
                            if (_x < 0 || _y < 0 || _x >= row || _y >= col) continue;
                            if (visited[_x, _y] != 0 || Math.Abs(land[current.x, current.y] - land[_x, _y]) > height) continue;
                            visited[_x, _y] = num;
                            que.Enqueue((_x, _y));
                        }
                    }
                    num++;
                }
            }
        }

        List<(int u, int v, int w)> edges = new List<(int u, int v, int w)>();

        // 그래프 생성
        for (var i = 0; i < row; i++)
        {
            for (var j = 0; j < col; j++)
            {
                var _x = i + 1;
                if (_x < row)
                {
                    if (visited[i, j] != visited[_x, j])
                        edges.Add((visited[i, j], visited[_x, j], Math.Abs(land[i, j] - land[_x, j])));
                }
                var _y = j + 1;
                if (_y < col)
                {
                    if (visited[i, j] != visited[i, _y])
                        edges.Add((visited[i, j], visited[i, _y], Math.Abs(land[i, j] - land[i, _y])));
                }
            }
        }

        edges.Sort((a, b) =>
        {
            return a.w - b.w;
        });

        // MST 구하기
        int[] union = new int[num];
        for (var i = 0; i < num; i++)
        {
            union[i] = i;
        }

        int count = 0;
        for (var i = 0; i < edges.Count; i++)
        {
            var current = edges[i];
            if (find(current.u, union) != find(current.v, union))
            {
                union[find(current.v, union)] = find(current.u, union);
                count++;
                answer += current.w;
            }
            if (count == num - 2) break;
        }

        return answer;
    }

    int find(int x, int[] union)
    {
        if (union[x] != x)
        {
            union[x] = find(union[x], union);
        }
        return union[x];
    }
}

결과

정확성 테스트

테스트 1 〉	통과 (1.89ms, 31.2MB)
테스트 2 〉	통과 (3.02ms, 31.3MB)
테스트 3 〉	통과 (2.77ms, 31.3MB)
테스트 4 〉	통과 (2.99ms, 31.2MB)
테스트 5 〉	통과 (2.77ms, 31.2MB)
테스트 6 〉	통과 (2.95ms, 31.3MB)
테스트 7 〉	통과 (3.02ms, 31.4MB)
테스트 8 〉	통과 (2.94ms, 31.5MB)
테스트 9 〉	통과 (3.02ms, 31.2MB)
테스트 10 〉	통과 (3.05ms, 31.5MB)
테스트 11 〉	통과 (3.03ms, 31.2MB)
테스트 12 〉	통과 (2.73ms, 31.1MB)
테스트 13 〉	통과 (3.06ms, 31.1MB)
테스트 14 〉	통과 (3.08ms, 31.4MB)
테스트 15 〉	통과 (3.18ms, 31.5MB)
테스트 16 〉	통과 (4.32ms, 31.6MB)
테스트 17 〉	통과 (8.60ms, 32.4MB)
테스트 18 〉	통과 (8.53ms, 32.2MB)
테스트 19 〉	통과 (7.91ms, 31.8MB)
테스트 20 〉	통과 (31.08ms, 36.6MB)
테스트 21 〉	통과 (34.69ms, 37.1MB)
테스트 22 〉	통과 (67.13ms, 41.9MB)
테스트 23 〉	통과 (69.01ms, 42.1MB)
테스트 24 〉	통과 (7.52ms, 32.9MB)
테스트 25 〉	통과 (11.47ms, 33.3MB)
테스트 26 〉	통과 (65.90ms, 41.6MB)
테스트 27 〉	통과 (66.87ms, 41.4MB)
테스트 28 〉	통과 (60.82ms, 41.8MB)
테스트 29 〉	통과 (59.57ms, 41.7MB)
테스트 30 〉	통과 (71.62ms, 41.7MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0

 

오답노트

 처음 인접 그래프를 만들 때, 각 구역에서 인접 구역으로 가는 모든 간선들 중 최소 가중치를 가지는 간선만 남기려고 했다.

 각 구역들을 노드로 가지는 그래프를 생성, 초기화한 다음에 인접한 구역으로 이어지는 최소 간선만을 택하고자 했다.

 최악의 경우 지도의 모든 칸이 사다리 없이는 이동할 수 없는 독립된 구역으로 나뉠 수 있고, 이 경우 그래프 생성 및 초기화에 O(n^2), 각 구역마다 최소 간선을 찾는데 다시 O(n^2)가 되어 너무 복잡해졌다.

 결국 위에서와 같이 그래프를 따로 생성하지 않고, 최소 간선이 아니라 모든 간선을 기록함으로써 시간복잡도를 O(n)으로 줄였다.