[프로그래머스] 튜브의 소개팅

문제 설명

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

문제 풀이

• 생각이 필요한 BFS 문제이다.
• BFS의 큐대신에 대화시간이 작을수록 우선하는 우선순위큐를 이용해서 BFS를 진행한다.
• 위 행위의 의미는 대화시간의 제한이 존재하여 대화시간을 초과하면 더이상 진행할 수 없으므로 거리가 멀더라도 최종 위치에 도달 가능한 케이스를 우선 먼저 고려하겠다는 뜻이다.
• 이후, chk[X][Y]배열을 통해 각 위치에 도달가능한 최소거리를 저장한다.
• 이를 통해서 대화시간이 적은것 우선으로 진행시키되, 각 칸에 최소거리로 도착 가능한 케이스를 고려할 수 있으므로 원하는 결과를 얻을 수 있다.
• 진행 중 대화시간은 int형을 초과할 수 있으므로 long형 연산을 해야한다.

소스 코드 (JAVA)

import java.util.*;

class Solution {

    public class Point implements Comparable<Point>{
        int x, y, d, s;

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

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

    public int[] solution(int m, int n, int s, int[][] time_map) {
        //초기화
        int[] dx = {0,0,1,-1};
        int[] dy = {1,-1,0,0};
        int[][] chk = new int[m][n];
        for (int i = 0; i < m; i++) Arrays.fill(chk[i], Integer.MAX_VALUE);
        PriorityQueue<Point> q = new PriorityQueue<>();
        q.add(new Point(0,0,0,0));

        int[] result = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE};
        while(!q.isEmpty()) {
            Point cur = q.poll();
            if (cur.x == m-1 && cur.y == n-1) {
                if (cur.d < result[0]
                        || (cur.d == result[0] && cur.s < result[1])) {
                    result[0] = cur.d;
                    result[1] = cur.s;
                }
                continue;
            }
            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 >= m || Y >= n) continue;
                if (time_map[X][Y] == -1) continue;
                int newD = cur.d + 1;
                long newS = (long)cur.s + (long)time_map[X][Y];
                //제한 시간 넘기는지 확인
                if (newS > s) continue;
                //최소 거리보다 작거나 큰지 확인 
                if (chk[X][Y] <= newD) continue;
                chk[X][Y] = newD;
                q.add(new Point(X, Y, newD, Math.toIntExact(newS)));
            }
        }
        return result;
    }
}