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

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

주어진 조건에 따라 최소 비용으로 모든 지형을 갈 수 있는 사다리를 놓는 경우 비용의 총합을 구하는 문제

- 모든 지형을 탐색할 때까지 1, 2번을 반복

 

1. 사다리 없이 갈 수 있는 지형 탐색

- BFS 알고리즘을 이용해 현재 갈 수 있는 지형을 탐색

- 사다리 없이 갈 수 없는 지형은 우선순위 큐에 담아 놓음

 

2. 최적의 위치에 사다리를 놓음

- 1번 탐색이 종료되는 시점에 탐색된 지형에서 사다리를 놓아야 갈 수 있는 지형이 우선순위 큐에 담겨있게 됨

- 이미 탐색된 지형이 우선순위 큐 안에 들어있을 수 있기 때문에, 탐색되지 않은 지형이 나올 때까지 Dequeue()

 

BFS 알고리즘

https://godgjwnsgur7.tistory.com/47

[Algorithm C#] BFS, DFS ( + Back Tracking )

 

우선순위 큐

https://learn.microsoft.com/ko-kr/dotnet/api/system.collections.generic.priorityqueue-2?view=net-8.0

PriorityQueue<TElement,TPriority> 클래스 (System.Collections.Generic)

+ 일반적인 코딩테스트 환경은 C#의 우선순위 큐가 생기기 전의 버전이기 때문에 따로 구현 해서 사용해야 함

 

주석 참조

    using System;
    using System.Collections.Generic;

    public class Solution
    {
        public struct Pos
        {
            public int y;
            public int x;

            public Pos(int y, int x)
            {
                this.y = y;
                this.x = x;
            }
        }

        public int solution(int[,] land, int height)
        {
            int answer = 0;
            int length = land.GetLength(0);
            int count = length * length; // 모든 지형의 수
            int currCount = 0; // 현재 갈 수 있는 지형의 수

            var dirY = new int[4] { 0, 0, 1, -1 };
            var dirX = new int[4] { 1, -1, 0, 0 };
            var boolArrays = new bool[length, length]; // 방문배열
            PriorityQueue pq = new PriorityQueue(); // 커스텀 우선순위큐

            // 초기 값 세팅 (0,0) 좌표에서 탐색 시작
            var queue = new Queue<Pos>();
            queue.Enqueue(new Pos(0, 0));
            boolArrays[0, 0] = true;
            currCount = 1;

            // 모든 지형을 탐색할 때까지 반복
            while (currCount != count)
            {
                // 1. 사다리 없이 갈 수 있는 지형 탐색
                while (queue.Count > 0)
                {
                    Pos currPos = queue.Dequeue();

                    for (int i = 0; i < 4; i++)
                    {
                        Pos movePos = new Pos(currPos.y + dirY[i], currPos.x + dirX[i]);

                        // 범위 벗어남
                        if (movePos.y < 0 || movePos.y >= length ||
                           movePos.x < 0 || movePos.x >= length)
                            continue;

                        // 이미 탐색한 지형
                        if (boolArrays[movePos.y, movePos.x])
                            continue;

                        int cost = Math.Abs(land[currPos.y, currPos.x] - land[movePos.y, movePos.x]);
                        if (cost <= height)
                        {
                            // 이동이 가능한 경우
                            boolArrays[movePos.y, movePos.x] = true;
                            queue.Enqueue(movePos);
                            currCount++;
                        }
                        else
                        {
                            // 이동이 불가능한 경우
                            DataClass dataClass = new DataClass(movePos, cost);
                            pq.Enqueue(dataClass);
                        }
                    }
                }

                // 최적 위치에 사다리 설치
                if (currCount != count)
                {
                    Pos movePos = new Pos(0, 0);
                    int cost = 0;
                    
                    // 최적 위치 찾기
                    while (pq.Count > 0)
                    {
                        DataClass dataClass = pq.Dequeue();
                        
                        if (boolArrays[dataClass.pos.y, dataClass.pos.x] == false)
                        {
                            movePos = dataClass.pos;
                            cost = dataClass.cost;
                            break;
                        }
                    }
                    
                    // 사다리를 설치해 갈 수 있게 된 지형 추가
                    answer += cost;
                    queue.Enqueue(movePos);
                    boolArrays[movePos.y, movePos.x] = true;
                    currCount++;
                }
            }

            return answer;
        }
        
        // 우선순위 큐의 기준이 되는 데이터
        public class DataClass
        {
            public Pos pos;
            public int cost;

            public DataClass(Pos pos, int cost)
            {
                this.pos = pos;
                this.cost = cost;
            }
        }
        
        // 커스텀 우선순위 큐 cost를 기준으로 최소 값을 반환하는 자료형
        public class PriorityQueue
        {
            private List<DataClass> heap = new List<DataClass>();

            public int Count => heap.Count;

            public void Enqueue(DataClass 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
                    DataClass temp = heap[now];
                    heap[now] = heap[next];
                    heap[next] = temp;
                    now = next;
                }
            }

            public DataClass Dequeue()
            {
                DataClass ret = heap[0]; // 리턴 값
                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; 
                    
                    if (next == now)
                        break;

                    DataClass temp = heap[now];
                    heap[now] = heap[next];
                    heap[next] = temp;

                    now = next;
                }

                return ret;
            }
        }
    }