<Lv.4> 지형 이동 (프로그래머스 : C#)

https://school.programmers.co.kr/learn/courses/30/lessons/62050

📕 문제 설명

모든 칸을 방문하기 위해 필요한 최소 사다리 설치 비용 반환하기

칸은 상하좌우로 이동가능하며 칸을 방문하기 위해서는 현재 칸과의 높이차가 height 이하여야 한다. 차이가 그 이상인 경우에는 두 높이차의 비용이 드는 사다리를 설치해야한다.

(출발은 아무칸에서 시작하며, 설치한 사다리는 철거하지 않는다.)

• Input
  각 격자칸의 높이, 이동 가능한 최대 높이차 (height)
• Output
  모든 칸을 방문하기 위해 필요한 최소 사다리 설치 비용

예제

풀이

최소힙을 활용해서 사다리를 세우는 최소 비용이 계속해서 뽑히도록 하면서 모든 칸을 방문하면 끝내도록 하였다.

1) 사다리를 세우지 않고도 갈 수 있는 것들끼리 index를 매겨둔 color라는 배열을 만들었다.
2) 최소힙을 만든 후 color가 같은 애들은 cost를 0으로, color가 다른 애들은 height를 계산해서 넣어준다.
3) 최소힙에서 계속 Dequeue를 하는 과정에서 가장 비용이 낮은 것들이 계속 뽑히고, 해당 칸이 방문되면서 color가 같은 것들은 cost가 0으로 잡히므로 다 방문이 된다. 즉, color가 다른 것들에 대해 비용이 알아서 최소로 잡히게 된다.
4) 모든 칸을 방문하면 최소 비용을 더한 결과를 반환한다.

(+ color index 방문 배열두고 다 방문하면 while문 탈출하면 시간 살짝 더 빠르게 할 수 있을것같기도?)

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int[,] land, int height) {
        int answer = 0;
        int n = land.GetLength(0);
        int m = land.GetLength(1);
        
        bool[,] visited = new bool[n,m];
        int[,] color = new int[n,m];
        int colorIndex = 0;
        
        int[] dirX = new int[] {0, 0, 1, -1};
        int[] dirY = new int[] {1, -1, 0, 0};
        
        // 같은색 표시 (사다리 없이 방문 가능한 애들끼리 index 매기기)
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (!visited[i, j])
                {
                    Queue<(int, int)> queue = new Queue<(int, int)>();
                    queue.Enqueue((i, j));
                    while (queue.Count >= 1)
                    {
                        (int currX, int currY) = queue.Dequeue();
                        if (visited[currX, currY]) continue;
                        visited[currX, currY] = true;
                        color[currX, currY] = colorIndex;
                        int currHeight = land[currX, currY];
                        for (int d = 0; d < 4; d++)
                        {
                            int newX = currX + dirX[d];
                            int newY = currY + dirY[d];
                            // 범위 안벗어나면서 높이차가 height 이하인 경우
                            if (newX >= 0 && newX < m && newY >= 0 && newY < n && Math.Abs(currHeight - land[newX, newY]) <= height)
                            {
                                queue.Enqueue((newX, newY));
                            }
                        }
                    }

                    colorIndex += 1;
                }
            }
        }
        
        // minHeap에 (최소비용, x, y) 저장 
        // 최소 비용 순서대로 나와서 자연스레 제일 낮은 비용들 찾게됨
        // 같은 색인 경우는 비용 0으로 설정, 모두 방문하면 끝
        PriorityQueue pq = new PriorityQueue();
        pq.Enqueue(new Node(){cost=0, x= 0, y = 0});
        visited = new bool[n,m]; // visited bool 배열 초기화 
        
        while (pq.Count >= 1)
        {
            Node currNode = pq.Dequeue();
            int currX = currNode.x;
            int currY = currNode.y;
            if (visited[currX, currY]) continue;
            
            visited[currX, currY] = true;
            answer += currNode.cost;
            
            for (int d = 0; d < 4; d++)
            {
                int newX = currX + dirX[d];
                int newY = currY + dirY[d];

                if (newX >= 0 && newX < m && newY >= 0 && newY < n)
                {
                    int cost = 0;
                    if (color[currX, currY] != color[newX, newY]) // 사다리 세워야하는 경우 cost 계산 (높이차)
                    {
                        cost = Math.Abs(land[currX, currY] - land[newX, newY]);
                    }
                    Node newNode = new Node(){cost=cost,x=newX,y=newY};
                    pq.Enqueue(newNode);
                }
            }
            
        }

        return answer;
    }
}

public struct Node
{
    public int cost;
    public int x;
    public int y;
}

public class PriorityQueue // minHeap (비용이 기준)
{   
    private List<Node> heap = new List<Node>();

    public int Count => heap.Count;
    
    public void Enqueue(Node data)
    {
        heap.Add(data);
        int now = heap.Count - 1; // 추가한 노드 위치 (트리 마지막 레벨 왼쪽)
        
        while (now > 0) // 순서 지정하기
        {
            int next = (now - 1) / 2; // 부모 노드 (트리)
            if (heap[now].cost > heap[next].cost) break;
            // 부모노드보다 추가한게 작으면 Swap
            Node temp = heap[now];
            heap[now] = heap[next];
            heap[next] = temp;
            now = next;
        }
    }
    
    public Node Dequeue()
    {
        Node ret = heap[0]; // return할 값 (트리 root에 max 저장해둔 형태)
        int lastIndex = heap.Count - 1;
        heap[0] = heap[lastIndex];
        heap.RemoveAt(lastIndex);
        lastIndex -= 1;
        int now = 0;
        
        while (true)
        {
            int left = 2 * now + 1;
            int right = 2 * now + 2;
            int next = now;
            
            if (left <= lastIndex && heap[next].cost > heap[left].cost) next = left; // 왼쪽보다 크면 왼쪽으로 보내기
            if (right <= lastIndex && heap[next].cost > heap[right].cost) next = right; // 오른쪽보다 크면 오른쪽으로 보내기 (여기서는 위에 now랑 left랑 비교해서 더 큰애랑 또 비교해서 갱신하게됨)
            if (next == now) break;
            
            Node temp = heap[now];
            heap[now] = heap[next];
            heap[next] = temp;
            
            now = next;
        }
        
        return ret;
    }
}

결과