[프로그래머스] 지형 이동

문제 설명

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

문제 풀이

• BFS, Heap을 이용하여 풀이하였다.
• 풀이는 다음과 같다.

  BFS를 위한 Queue와 사다리를 설치할 후보를 넣어줄 높이 차이로 정렬된 PriorityQueue(이하 PQ)를 준비한다.

  1. BFS를 진행하되 다음과 같은 두가지 케이스를 고려한다.
     1. height 이하로 진행 가능한 경우 -> Queue에 넣어주고 BFS 계속 진행
     2. height 초과로 사다리 설치 필요한 경우 -> PQ에 넣어주고 BFS 계속 진행
  2. BFS를 완료하면 방문하지 않은 지점이 나올때까지 PQ에서 poll해주고 방문하지 않은 지점이 나올 경우 Queue에 넣어준다.

• 위의 1, 2번 과정을 반복하면 최소 비용으로 전체 지점 방문이 가능하다.

소스 코드 (JAVA)

import java.util.*;
class Solution {
    public class Point implements Comparable<Point>{
        int x, y, diff;

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

        @Override
        public int compareTo(Point o) {
            return this.diff - o.diff;
        }
    }

    public int solution(int[][] land, int height) {
        int N = land.length;
        int[] dx = {0,0,1,-1};
        int[] dy = {1,-1,0,0};
        Queue<Point> q = new ArrayDeque<>();
        PriorityQueue<Point> pq = new PriorityQueue<>();
        boolean[][] chk = new boolean[N][N];

        //BFS 시작
        pq.add(new Point(0,0,0));

        int result = 0;
        while(!pq.isEmpty()) {
            //pq에서 diff가 가장 작은 지점 뽑아옴
            while(!pq.isEmpty()) {
                Point cur = pq.poll();
                if (chk[cur.x][cur.y]) continue;
                //이미 방문한 지점이 아니면 결과 올려주고 q에 넣어줌
                result += cur.diff;
                chk[cur.x][cur.y] = true;
                q.add(cur);
                break;
            }

            //height 이하로 갈 수 있는 경우는 계속 진행
            //height 넘어서는 경우 pq에 넣어줌
            while(!q.isEmpty()) {
                Point cur = q.poll();
                for (int d = 0; d < 4; d++) {
                    int X = cur.x + dx[d];
                    int Y = cur.y + dy[d];
                    if (X < 0 || Y < 0 || X >= N || Y >= N || chk[X][Y]) continue;
                    int diff = Math.abs(land[cur.x][cur.y] - land[X][Y]);
                    //height 초과인 경우 -> pq에 넣어줌
                    if (diff > height) {
                        pq.add(new Point(X, Y, diff));
                    }
                    //height 이하인 경우 -> q에 넣어줌
                    else {
                        chk[X][Y] = true;
                        q.add(new Point(X, Y, 0));
                    }
                }
            }
        }
        return result;
    }
}