등산코스 정하기(프로그래머스) JAVA

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

프로그래머스

문제 설명

• 산의 출입구, 쉼터, 산봉우리를 알려준다. 그때 등산코스를 짜야한다.
• 이 때, 등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있다. 
• 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 intensity라고 부른다.
• 등산코스는 출입구에서 시작해서 산봉우리를 한 번 들리고 나서 다시 출입구로 복귀 해야 한다.
• 이때 intensity가 최소가 되도록 등산코스를 정해야 한다.
• 그 때 산봉우리 index와 intensity 값을 출력해야 한다!!
• 만약 intensity가 같은 것이 여러개라면 index가 더 작은 것을 출력한다.

이 때 intensity = 5이다.

이 때 intensity = 3이다.

그러므로 intensity가 가장 낮은 등산코스의 intensity = 3 이다!!

 

입력값

• int n : 노드의 수
• int [][] paths : 길이 주어짐
• int [] gates : 출발점
• int [] summits : 산봉우리

 

문제에 대한 아이디어

제일 처음 생각한 아이디어는 DFS로 각 출발점 부터 시작해서 intensity가 최소인 부분을 찾고 그 때의 산봉우리를 체크하는 것이다. 모든 테스트케이스도 성공했지만 17, 18, 19, 20 번 체점이 실패 했다.

그래서 유튜브에 강의 영상을 보았다. 유튜브에 강의를 클릭하면 참고한 강의를 볼 수 있다.

 

디익스트라로 풀기

한개의 출발점에서 시작해서 여러개의 산봉우리를 도착 할 때의 weight의 최대값을 찾는 문제이므로 디익스트라를 사용해서 문제를 풀면 된다. 디익스트라는  1 : N 관계에서 자주 쓰인다. 

 

만들어야 할 것은 방문할 Edge들과 방문한 Edge 산봉우리를 check 할 수 있는 것과 그래프를 저장할 요소들이다.

• 방문할 Edge는 시작하는 부분이 더 작은 곳부터 탐색하기 위해서 PriorityQueue로 만든다.
• 방문한 Edge는 HashSet을 사용해 방문했는지 check 한다.
• 산봉우리에 도착했는지 check는 HashSet을 사용해 산봉우리에 도착했는지 Check 한다.
• HashMap<Integer, ArrayList<Edge>> edegs의 형태로 edge를 저장한다. 
• 여기서 Edge는 to(시작) fr(도착) wt(값) 이렇게 3개가 존재한다. 

출발선에서 부터 시작해서 산봉우리를 도착할 때 까지 탐색한다. 이 때 intensity는 

 int intensity = Math.max(e.wt, map[e.fr]);

현재의 weight와 지금 출발지점 까지의 최대 weight를 비교해주면 된다.

if(intensity < map[e.to])
      map[e.to] = intensity;

도착지점은 거기까지 도착한 모든 경로중 intensity가 최소인 것이 들어가야 하므로 현재 intensity가 도착한 곳의 최대 intensity보다 작으면 변경해 준다. 

 

 

구현

• Edge

class Edge implements Comparable<Edge> {
    public int fr, to, wt; // 출발, 도착, 값
    
    public Edge(int i, int j, int w){
        fr = i;
        to = j;
        wt = w;
    }
    
    public int compareTo(Edge e){
        if(this.wt == e.wt) //현재 wt가 같으면 도착지점 중 작은 것을 선택
            return Integer.compare(this.to, e.to);
        return Integer.compare(this.wt, e.wt); // wt가 작은 것을 선택
    }
}

• 사용하는 것

int [] map;
PriorityQueue<Edge> visit = new PriorityQueue<>(); //방문할 Edge
HashSet<Integer> visited = new HashSet<>(); //방문한 Edge
HashSet<Integer> summits = new HashSet<>(); //산봉우리 check
HashMap<Integer, ArrayList<Edge>> edges = new HashMap<>();

• Main

public int[] solution(int n, int[][] paths, int[] gates, int[] _summits) {
        visit.clear();
        visited.clear();
        edges.clear();
        map = new int[n+1]; // 현재 intensity의 최솟값
        Arrays.fill(map, Integer.MAX_VALUE);  
        
        Edge answer = new Edge(-1,-1,Integer.MAX_VALUE); //정답 edge
        
        for(int s : _summits)
            summits.add(s); //모든 산봉우리를 집어 넣는다.
            
        for(int[] p : paths){
            //양방향 그래프
            Edge e1 = new Edge(p[0],p[1],p[2]); 
            Edge e2 = new Edge(p[1],p[0],p[2]);
            
            if(!edges.containsKey(p[0]))
                edges.put(p[0], new ArrayList<Edge>());
            if(!edges.containsKey(p[1]))
                edges.put(p[1], new ArrayList<Edge>());
                
            edges.get(p[0]).add(e1); //Key가 2 {2,3,5} {2,4,2} .. 이렇게 들어감 
            edges.get(p[1]).add(e2);
        }
        
        for(int gate : gates){
            visit.addAll(edges.get(gate)); //출발하는 모든 edge를 집어넣음
            //모든 edge를 집어 넣어도 되는 이유, 디익스트라는 1 : N인데 어떻게?
            //이 문제는 gates를 원하지 않는다. 어디서 출발했는지를 원하지 않는다.
            //우리는 가상의 노드에서 출발했다고 생각하고 그 노드가 gates와 이어졌다고 생각한다.
            visited.add(gate);
            map[gate] = 0;
        }
        
        //디익스트라 실행부분
        while(!visit.isEmpty()){
            Edge e = visit.poll();
            if(visited.contains(e.to)) continue; // 도착지점을 방문했으면 넘어감
            
            int intensity = Math.max(e.wt, map[e.fr]); 
            if(intensity < map[e.to])
                map[e.to] = intensity;
            
            if(summits.contains(e.to)){ //산봉우리 도착
                Edge eSummit = new Edge(0, e.to, intensity); //그때 결과값
                if(answer.compareTo(eSummit) > 0) //만약 answer보다 현재 intensity가 더 작으면
                    answer = eSummit;
                continue;
            }
            
            visit.addAll(edges.get(e.to)); //현재 도착지점에서 갈 수 있는 모든지점을 넣음
            visited.add(e.to); // 도착지점을 방문했다고 저장
        }
        return new int[]{answer.to, answer.wt};
    }

gate를 모두 다 넣어도 되는 이유!!