2022 KAKAO TECH INTERNSHIP - 등산코스 정하기 (JAVA)

❓ 문제 - 2022 KAKAO TECH INTERNSHIP 등산코스 정하기- JAVA 풀이법

출처

(https://school.programmers.co.kr/learn/courses/30/lessons/118669)

프로그래머스

 

 

 

📝 문제해결법

1. 문제

• 출발구 ~ 산봉우리 ~ 출발구 까지의 하나의 등산 코스에서 각 지점을 지날 때 cost 중 최대 값을 그 등산코스의 intensity이다.
• 여러 등산 코스 중 최소의 intensity 산봉우리 번호를 구하고, 만약 intensity가 같다면 최소 산봉우리를 구하여라. 

 

2. 해결 방법

• 제한 사항이 n이 최대 50000이고, paths의 길이가 최대 200,000이므로 일반 dfs로 풀면 시간초과가 걸린다. 따라서 다익스트라와 intensity를 저장할 수 있는 dp를 이용해서 답을 구해야 한다.
• 문제에서 등산 코스에서는 출발구 ~ 산봉우리 ~ 출발구까지를 하나의 등산코스로 보지만, 출발구 ~ 산봉우리까지의 최소 intensity를 구하면 산봉우리 ~ 출발구를 구해도 똑같이 최소 intensity 구해지므로 출발구 ~ 산봉우리까지만 구하면 된다.
• 우선 일반 다익스트라 처럼 ArrayList를 배열로 만들어서 i번째 인덱스에는 i의 지점에 연결된 다른 노드의 지점의 번호와 cost를 저장한다.
  • 이때, 만약 paths의 s -> e 갈 때 들어갈 비용을 c라고 하면, 출발구 ~ 산봉우리로 구해야하고, 중간에 출발구나 산봉우리가 있으면 안되고, 출발구나 산봉우리가 아닌 경우 양방향 이동이 가능하다.
  • 따라서 다음과 같이 s가 출발이거나 e가 산봉우리이면 s -> e로, e가 산봉우리이거나 s가 출발지점이면 e -> s의 단방향의 path만 list에 넣고, 그 외의 경우라면 양방향 이동이 가능하도록 list에 넣어준다.
• 일반 다익스트라로 구현하며 intensity에 distance처럼 값을 저장한다.
• queue에 값을 넣을 때 연결되어 있고 만약 현재 노드 지점을 거쳐 연결된 지점으로 이동할 때 계산된 intensity가 원래 연결된 지점에 저장된 intensity[next.a]보다 작다면 작은 값으로 갱신해준다.
• 마지막에 intensity가 같은 경우도 있으므로,  산봉우리 숫자를 기준으로 오름차순으로 정렬하고 intensity가 작은 경우로 answer에 산봉우리 숫자, 최소 intensity를 구한다.

3. 느낀점

• 처음에 DFS+DP로만 구했는데 이게 DP를 잘 활용하지 못 해서 자꾸 시간초과랑 메모리 초과가 났다..
• 그래서 카카오 해설을 봤는데 다익스트라 + DP로 해결한다는 것을 보고 빨리 수정을 했는데 자꾸 이상한 값이 나왔다.
• 내가 우려했던 부분은 출발구 ~ 산봉우리 사이에 만약 출발구나 산봉우리가 있다면 어떻게 처리하지 였는데... 다른 사람의 코드를 보니 list에 path에 대한 정보를 넣을 때 a지점 -> b지점의 path를 경우를 나누어서 저장한다는 것을 보고 의문이 해결이 되었다..
• 출발구 -> 산봉우리라는 명확한 출발지와 도착지에 cost를 구하는 문제이므로 다익스트라로 풀어도 되는 구나라고 깨달았다..!!!
• 2일 동안 끙끙 거렸는데 정말 좋은 문제를 푼 것 같다..

 

💻 소스코드 (JAVA)

import java.util.*;

class Solution {
    public static class Node {
        public int a;
        public int cost;
        public Node(int a, int cost){
            this.a = a;
            this.cost = cost;
        }
    }
    public static ArrayList<Node>[] list;
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        list = new ArrayList[n+1];
        for(int i=0;i<=n;i++){
            list[i] = new ArrayList<Node>();
        }
        
        for(int[] path:paths){
            int s = path[0];
            int e = path[1];
            int c = path[2];
            if(isGate(s, gates) || isSummit(e, summits)){
                list[s].add(new Node(e, c));
            } else if(isGate(e, gates) || isSummit(s, summits)){
                list[e].add(new Node(s, c));
            } else {
                list[s].add(new Node(e, c));
                list[e].add(new Node(s, c));
            }
        }
                      
                      
        return dijkstra(n, gates, summits);
    }
                      
    public static int[] dijkstra(int n, int[] gates, int[] summits){
        Queue<Node> q = new LinkedList<>();
        int[] intensity = new int[n+1];
        
        Arrays.fill(intensity, Integer.MAX_VALUE);
        for(int g:gates){
            intensity[g] = 0;
            q.add(new Node(g, 0));
        }
        
        while(!q.isEmpty()){
            Node node = q.poll();
            
            if(node.cost > intensity[node.a]) continue;
            for(int i=0;i<list[node.a].size();i++){
                Node next = list[node.a].get(i);
                int temp = Math.max(intensity[node.a], next.cost);
                if(intensity[next.a] > temp){
                    intensity[next.a] = temp;
                    q.add(new Node(next.a, temp));
                }
            }   
        }

        int[] answer = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE};
        Arrays.sort(summits);
        for(int s:summits){
            if(intensity[s] < answer[1]){
                answer[0] = s;
                answer[1] = intensity[s];
            }
        }
        
        return answer;
    }
    
    
    public static boolean isGate(int g, int[] gates){
        for(int gate:gates){
            if(g == gate) return true;
        }
        
        return false;
    }
    
    public static boolean isSummit(int s, int[] summits){
        for(int summit:summits){
            if(s == summit) return true;
        }
        return false;
    }
    
}