[99클럽 코테 스터디 31일차 TIL] 힙

📖 오늘의 학습 키워드
힙 (다익스트라)

오늘의 회고

문제

[Minimum Cost of a Path With Special Roads]
https://leetcode.com/problems/minimum-cost-of-a-path-with-special-roads/description/

나의 해결

class Solution {
    public int dist(int x1, int y1, int x2, int y2) {
        return Math.abs(x2 - x1) + Math.abs(y2 - y1);
    }
    public int minimumCost(int[] start, int[] target, int[][] specialRoads) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        Set<Pair> visited = new HashSet<>(); 
        pq.offer(new int[]{start[0], start[1], 0});
        while(!pq.isEmpty()){
            int[] now = pq.poll();
            int x = now[0];
            int y = now[1];
            int cost = now[2];
            if(x == target[0] && y == target[1]) {
                return cost;
            }
            Pair p = new Pair(x, y);
            if(!visited.contains(p)){
                visited.add(p);
                pq.offer(new int[]{target[0], target[1], cost + dist(x, y, target[0], target[1])});
                for(int[] r: specialRoads) {
                    if(!visited.contains(new Pair(r[2], r[3]))) {
                        pq.offer(new int[]{r[2], r[3], cost +  dist(x, y, r[0], r[1]) + r[4]});
                    }
                }
            }
        }
        return 0;
    }
}

1. dist 함수는 (x1, y1)에서 (x2, y2)로 가기 위한 비용을 계산한다.
2. 우선순위 큐 pq를 생성하여 좌표와 해당 좌표에 도달하기 위한 비용을 저장한다.
   여기서 우선순위는 비용이며, 비용이 적을수록 우선순위가 높다.
3. 좌표에 대한 방문 처리를 하기 위해 HashSet에 방문한 좌표를 Pair로 저장한다.
4. pq에 시작 지점의 좌표와 비용 0을 삽입한다.
5. pq가 빌 때까지 다음 과정을 반복한다.
   1. 우선순위가 가장 높은 지점(도달하는데 최소 비용 필요)을 now로 가져오고 pq에서 삭제한다.
   2. now의 x 좌표와 y 좌표가 target 지점과 같다면 현재 비용을 반환한다.
   3. 현재 지점을 방문하지 않았다면 visited에 현재 좌표를 추가해 방문 처리를 한다.
   4. pq에 target 지점의 좌표와 현재 지점에서 target 지점까지 가는 데 필요한 비용을 삽입한다.
   5. specialRoads를 순회하며 각 road에서의 도착 지점을 아직 방문하지 않았다면, pq에 해당 지점의 좌표와 현재 지점에서 해당 지점까지 도달하는 데 필요한 비용을 삽입한다.