등산 코스 정하기

문제

프로그래머스

위와 같은 등산코스가 주어진다. 파란색은 출입구이고, 빨간색은 정상이다.

출입구에서 시작해서 정상까지 가는 동안 최소 비용으로 가는 경로를 구하는 문제이다.

 

출입구는 항상 같은 번호여야 한다. 즉, 등산 코스 중 다른 출입구는 방문 할 수 없다.

정상은 한번만 방문 해야 한다.

 

예를 들어 

위와 같은 경로로 등산하면 비용은 5이다.(경로 중 가장 높은 금액)

위와 같은 경로로 등산하면 비용은 3이다. (경로 중 가장 높은 금액)

 

따라서 최소 비용는 3이다.

 

이 때 최소경로가 되는 등산코스에 포함된 정상 번호와 최소 비용을 차례 대로 정수 배열에 담아 return 해야 한다.

만약 최소 경로가 되는 등산코스가 여러개라면 그중 정상 번호가 가장 낮는 등산 코스를 선택한다.

---

문제의 핵심은 출입구와 정상은 단 방향, 일반 노드는 양방향 그래프로 만드는 것이다.

입구에서 정상까지 가는 경로가 최소이면 돌아오는 경로도 똑같이 최소인 경로로 돌아오면 되기 때문이다.

즉, 정상까지 가는 경우의 경로만 생각하면 된다.

또한 경로가 단조 증가하는 형태를 띄기 때문에 (A -> B -> C 의 경로의 시간이 3이라면 A -> B -> C -> D 경로의 시간이 3보다 작아질 수 없다)

 

따라서 다익스트라 코드를 다음과 같이 수정할 수 있다.

//다익스트라
if(dis[to] > dis[from] + weight)
	dis[to] = dis[from] + weigth;
    
//변형
if(intensity[to] > max(intensity[from], weight)
	intensity[to] = max(intensity[from], weight;

---

먼저 그래프 저장하는 자료구조를 만들어준다.

class Pair{
    int target;
    int cost;
    Pair(int target, int cost){
        this.target = target;
        this.cost = cost;
    }
}

List<List<Pair>>list = new ArrayList<>(); //그래프 정보 저장
for(int i=0;i<=n;i++)list.add(new ArrayList<>());

Set<Integer>gate = new HashSet<>(); //출입구 번호 저장
for(Integer i : gates)gate.add(i);
        
Set<Integer>summit = new HashSet<>(); //정상 번호 저장
for(Integer i : summits)summit.add(i);

for(int i = 0;i<paths.length;i++){
       int a = paths[i][0];
       int b = paths[i][1];
       int cost = paths[i][2];
            
       //출입구일 경우 다른 곳으로 갈 수 있는 단방향 그래프
       //정상일 경우 특정 한 곳에서 정상으로 가는 단방향 그래프
       if(gate.contains(a) || summit.contains(b))
            list.get(a).add(new Pair(b, cost));
       else if(gate.contains(b) || summit.contains(a))
            list.get(b).add(new Pair(a, cost));
       else{ //일반 등산로일 경우 양방향 그래프
            list.get(a).add(new Pair(b, cost));
            list.get(b).add(new Pair(a, cost));   
       }
}

 

이제 다익스트라를 진행해준다.

static int[] dijkstra(int n, int[] gates, int[] summits){
        Queue<Pair>q = new LinkedList<>();
        int[] intensity = new int[n+1]; //경로마다 시간을 저장해줄 배열
        
        Arrays.fill(intensity, Integer.MAX_VALUE);
        
        for(int gate : gates){ //출입구 처음에 모두 큐에 넣어줌
            q.add(new Pair(gate, 0));
            intensity[gate] = 0;
        }
        while(!q.isEmpty()){
            int cost = q.peek().cost;
            int node = q.peek().target;
            
            q.remove();
            
            if(cost > intensity[node])continue;
            
            for(int i = 0;i<list.get(node).size();i++){
                int v = list.get(node).get(i).target;
                int c = list.get(node).get(i).cost;
                
                int dis = Math.max(intensity[node], c);
                if(intensity[v] > dis){
                    intensity[v] = dis;
                    q.add(new Pair(v, dis));
                }
            }
        }
        
        int mn = Integer.MAX_VALUE; //정상 번호
        int mw = Integer.MAX_VALUE; //최소 비용
        
        Arrays.sort(summits); //정상 번호들을 한번 정렬(최소비용이 같을 경우 작은 정상 번호 출력때문)
        
        for(int summit : summits){
            if(intensity[summit] < mw){
                mn = summit;
                mw = intensity[summit];
            }
        }
        
        return new int[]{mn, mw};
    }

---

전체 코드이다.

import java.util.*;
class Solution {
    static int[]dis;
    static List<List<Pair>>list = new ArrayList<>();
    static boolean[]check;
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        int[] answer = {};
        for(int i=0;i<=n;i++)list.add(new ArrayList<>());
        
        Set<Integer>gate = new HashSet<>();
        for(Integer i : gates)gate.add(i);
        
        Set<Integer>summit = new HashSet<>();
        for(Integer i : summits)summit.add(i);
        
        for(int i = 0;i<paths.length;i++){
            int a = paths[i][0];
            int b = paths[i][1];
            int cost = paths[i][2];
            
            if(gate.contains(a) || summit.contains(b))
                list.get(a).add(new Pair(b, cost));
            else if(gate.contains(b) || summit.contains(a))
                list.get(b).add(new Pair(a, cost));
            else{ //일반 등산로일 경우
                list.get(a).add(new Pair(b, cost));
                list.get(b).add(new Pair(a, cost));   
            }
        }
        
        
        return dijkstra(n, gates, summits);
    }
    
    static int[] dijkstra(int n, int[] gates, int[] summits){
        Queue<Pair>q = new LinkedList<>();
        int[] intensity = new int[n+1];
        
        Arrays.fill(intensity, Integer.MAX_VALUE);
        
        for(int gate : gates){
            q.add(new Pair(gate, 0));
            intensity[gate] = 0;
        }
        while(!q.isEmpty()){
            int cost = q.peek().cost;
            int node = q.peek().target;
            
            q.remove();
            
            if(cost > intensity[node])continue;
            
            for(int i = 0;i<list.get(node).size();i++){
                int v = list.get(node).get(i).target;
                int c = list.get(node).get(i).cost;
                
                int dis = Math.max(intensity[node], c);
                if(intensity[v] > dis){
                    intensity[v] = dis;
                    q.add(new Pair(v, dis));
                }
            }
        }
        
        for(int i : intensity)System.out.print(i + " ");
        int mn = Integer.MAX_VALUE; //산봉우리 번호
        int mw = Integer.MAX_VALUE; //최솟값
        
        Arrays.sort(summits);
        
        for(int summit : summits){
            if(intensity[summit] < mw){
                mn = summit;
                mw = intensity[summit];
            }
        }
        
        return new int[]{mn, mw};
    }
}
class Pair{
    int target;
    int cost;
    Pair(int target, int cost){
        this.target = target;
        this.cost = cost;
    }
}