프로그래머스 | 등산코스 정하기 - java

프로그래머스

 

아직 못품 - 23, 25번 시간초과 환장하겠다 대체 뭘 더 고쳐줘야 만족하겠니?????????????????????????????????

 

풀었다!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

 

 

* path의 가중치값이 최대 10,000,000임. INF 값을 MAX_VALUE로 넉넉하게 잡아줘야함!!

- 괜히 1만 정도로 적게 잡고 풀다가 환장하는줄 알았다

 

* summit 배열 정렬  ㅡㅡ

- 출제자놈들 오름차순 정렬 안된 배열 넘겨주는거는 하도 많이 당해서 이제는 익숙할 정도다..  정렬 안해도 풀 수 있는 방법은 있겠지만 쉽게 풀기 위해서 정렬 해주는 것이 속편하다

 

import java.util.*;

class Solution {

    static final int INF = Integer.MAX_VALUE;

    private static class Node {
        int idx;
        List<Edge> edgeList = new ArrayList<>();

        public Node(int idx) {
            this.idx = idx;
        }
    }

    private static class Edge implements Comparable<Edge> {
        Node from;
        Node to;
        int weight;

        public Edge(Node from, Node to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return this.weight - o.weight;
        }
    }

    List<Node> nodeList = new ArrayList<>();
    Set<Integer> summitSet = new HashSet<>();
    Set<Integer> gateSet = new HashSet<>();
    PriorityQueue<Edge> queue = new PriorityQueue<>();
    int[] dp;  // dp[i]: i 노드까지 가는데 걸리는 최소 intensity 저장
    int ans;
    
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {

        // init
        for(int i = 0; i <= n; i++) {
            nodeList.add(new Node(i));
        }
        for (int[] path : paths) {
            Node from = nodeList.get(path[0]);
            Node to = nodeList.get(path[1]);

            // 양방향 연결
            Edge fromEdge = new Edge(from, to, path[2]);
            Edge toEdge = new Edge(to, from, path[2]);

            from.edgeList.add(fromEdge);
            to.edgeList.add(toEdge);
        }

        for (int gate : gates) {
            gateSet.add(gate);
        }
        for (int summit : summits) {
            summitSet.add(summit);
        }

        ans = INF;
        int min = INF;
        int ansIdx = 0;
        Arrays.sort(summits);
        dp = new int[nodeList.size()];

        for (int summit : summits) { // 산봉우리에서 각 노드로 가는 최단 intensity 계산
            Node v = nodeList.get(summit);
            dfs(v);
            for (int gate : gates) {
                min = Math.min(min, dp[gate]); // 산봉우리 -> gate 이동 최소 intensity
            }
            if(min < ans) {
                ans = min;
                ansIdx = summit;
            }
        }
        return new int[]{ansIdx, ans};
    }

    private void dfs(Node v) {
        Arrays.fill(dp, INF);
        dp[v.idx] = 0;

        queue.clear();

        // 시작 노드에서 갈 수 있는 Edge 삽입
        for (Edge edge : v.edgeList) {
            // 산봉우리 방향으로는 갈 수 없다!
            if(summitSet.contains(edge.to.idx)) continue;
            
            //////////////// 핵심 ////////////////////
            if(ans < edge.weight) continue; // 현재 최소 intensity보다 더 크면 볼 필요가 없음
            /////////////////////////////////////////
            
            dp[edge.to.idx] = edge.weight;
            queue.add(edge);
        }

        // 처음과 끝 이외에 출입구가 있으면 안된다! = 중간에 출입구를 거쳐 가면 안된다
        // 반드시 "원래의 출입구"로 돌아와야 한다 = (dp[출입구] * 2 로 구하면 최솟값을 구하면 되기 때문에 문제 X)
        while(!queue.isEmpty()) {
            // 이번에 이용할 Edge
            Edge w = queue.poll();

            // 현재 최소 intensity 보다 현재 경로의 가중치가 더 큰 경우 = 볼 필요 없다 (최단경로 성립 X)
            if(dp[w.to.idx] < w.weight) continue;

            // 내가 도착한 노드에서 다시 갈 수 있는 곳들
            for (Edge edge : w.to.edgeList) {
                // 산봉우리 방향으로는 갈 수 없다!
                if(summitSet.contains(edge.to.idx)) continue;

                // 현재 방문 노드까지의 최소 intensity 값 vs edge의 가중치 값
                int maxIntensity = Math.max(dp[w.to.idx], edge.weight);

                // 더 낮은 intensity 값으로 해당 노드를 방문할 수 있다면?
                if(maxIntensity < dp[edge.to.idx]) {
                    dp[edge.to.idx] = maxIntensity;
                    // 만약 도착 노드가 출입구라면 해당 노드 방향은 더이상 탐색 X (최솟값 갱신은 진행)
                    if(!gateSet.contains(edge.to.idx)) {
                        queue.add(edge);
                    }
                }
            }
        }
    }
}

 

 

 

하 진짜 사랑합니다

 

이거 못풀었으면 진짜로 억울해서 잠 못잘뻔했다

 

이렇게 문제 풀고나서 기뻤던 적은 처음이다

다른 사람들 코드 안보고 풀어서 그런가 너무 뿌듯하다. 

 

나 실력이 조금 늘었을지도??

 

내일 포스팅 하면서 정리해볼것