[프로그래머스] 합승 택시 요금, java

- 문제

프로그래머스

- 풀이

import java.util.*;

class Solution {
    static int N;
    static ArrayList<ArrayList<Node>> data;
    
    //다익스트라에 사용할 Node 클래스입니다.
    //이 Node를 가질 ArrayList의 index에서 n 까지의 요금 k로 가지는 class입니다.
    static class Node{
        int n, k;
        
        public Node(int n, int k){
            this.n = n;
            this.k = k;
        }
        
        public String toString(){
            return "n >> "+n+", "+"k >> "+k;
        }
    }
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        
        //최소값을 찾는 문제이기 때문에 int의 최대값을 넣어놓고 탐색을합니다.
        int answer = Integer.MAX_VALUE;
        
        //전역적으로 n의 값을 사용하기 위해 static으로 선언해놓은 N에 넣어줍니다.
        N = n;
        
        //주어진 각 지점간의 택시요금 정보를 담을 
        //ArrayList<ArrayList<Node>> 배열을 선언해줍니다.
        //이 역시 전역적으로 사용하기 위해 static으로 선언해주었습니다.
        data = new ArrayList<>();
        
        //data의 각 index에 비어있는 ArrayList를 채우는 밑작업을 합니다.
        for(int i=0; i<=n; i++){
            data.add(new ArrayList<>());
        }
        
        //이제 fares배열을 순회하며 각 지점간의 택시요금을 입력해줍니다.
        //택시요금은 양방향이 같으므로 양 방향에 입력해줍니다.
        for(int i=0; i<fares.length; i++){
            int[] now = fares[i];
            data.get(now[0]).add(new Node(now[1], now[2]));
            data.get(now[1]).add(new Node(now[0], now[2]));
        }
        
        //이제 다익스트라 알고리즘을 통해 각 지점까지의 최소 택시요금을 구합니다.
        //여기서는 시작점으로 주어진 s에서의 모든 지점까지의 택시요금들을 구하였습니다.
        int[] start = run(s);
        
        //먼저 시작점에서 방식 a, b가 갈라져 각자의 
        //집으로 가는 방식을 answer에 입력해 놓습니다.
        answer = Math.min(start[a]+start[b], answer);
        
        //이제 각 지점에서의 최단거리들을 찾고, 각자의 집으로 가는 최소 요금을 계산합니다.
        for(int i=1; i<=n; i++){
            
            //i가 시작점인 경우는 위에서 이미 확인했으므로 건너뜁니다.
            if(i==s) continue;
            
            //i에서 시작하여 모든 노드까지의 최소 택시요금을 찾아 now에 담습니다.
            int[] now = run(i);
            
            //시작점에서 i까지의 최소요금 + i에서 a까지의 최소요금 + i에서 b까지의 최소요금을 합쳐
            //현재의 최소 요금을 계산합니다.
            int nowMin = start[i] + now[a] + now[b];
            
            //이제 지금까지의 최소요금 answer와 nowMin을 비교하여 answer을 채워줍니다.
            answer = Math.min(nowMin, answer);
        }
        
        //답을 반환합니다.
        return answer;
    }
    
    //다익스트라 알고리즘을 통해
    //각 지점까지의 최소 가중치를 구해줍니다.
    //인자로 시작 지점의 위치 s를 받아줍니다.
    static int[] run(int s){
        
        //방문처리를 위한 visited 배열을 생성해줍니다.
        boolean[] visited = new boolean[N+1];
        
        //각 지점까지의 최소 가중치를 담아줄 val 배열을 선언해줍니다.
        int[] val = new int[N+1];
        
        //최소값을 구하는 것이 목적이므로, 초기값은 int의 최대값으로 채워넣습니다.
        Arrays.fill(val, Integer.MAX_VALUE);
        
        //우선순위 큐를 이용해 최소의 가중치를 가지는 객체를 우선으로 꺼내
        //각 까지의 지점의 최소요금을 찾아냅니다.
        //우선순위 큐를 사용함으로서, 큰 가중치의 이동을 뒤로 늦추며 적은 가중치로 각 지점까지의
        //요금을 미리 이동해 볼 수 있습니다.
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<>(){
            @Override
            public int compare(int[] a, int[] b){
                return a[1]-b[1];
            }
        });
        
        //이제 시작점 s는 가중치가 0이므로 표시해주고
        //pq에 추가해줍니다.
        val[s] = 0;
        pq.add(new int[]{s, 0});
        
        //while문을 통해 다익스트라 알고리즘을 시작합니다.
        while(!pq.isEmpty()){
            
            //이번 지점정보를 꺼내줍니다.
            int[] now = pq.poll();

            //만약 이번 지점에 이미 방문했었다면, 
            //다시 탐색할 필요가 없으므로 continue해줍니다.
            //이 과정을 안하면 몇몇 문제의 효율성 기준을 통과하지 못합니다.
            if(visited[now[0]]) continue;
            
            //처음 방문이라면 방문 처리를 해줍니다.
            visited[now[0]] = true;

            //현재 now[0]노드에서 갈 수 있는 모든 노드들을 하나씩 확인합니다.
            for(Node nxt : data.get(now[0])){
                
                //만약 해당 노드에 아직 도착한 적이 없고 &&
                //<해당 노드까지의 현재 최소요금보다, 지금 경로를 거쳐서 가는 요금이 더 적다면>
                if(!visited[nxt.n] && val[nxt.n] > nxt.k+now[1]){
                    
                    //해당 노드에 새로운 최소 요금을 갱신시켜줍니다.
                    val[nxt.n] = nxt.k+now[1];
                    //그리고 pq에 입력하여 탐색에 확인할 수 있도록 합니다.
                    pq.add(new int[]{nxt.n, val[nxt.n]});
                }
            }
        }
        
        //위의 과정을 통해 만들어진 최소요금 배열을 반환합니다.
        return val;
    }
}

 

만약 7, 8, 22, 23? 이러한 테스트케이스에서만 시간초과가 발생한다면, if(visited[now[0]]) continue; 부분과 같이 이미 탐색한 지점은 다시 노드 확인을 하지 않도록 한다면 해결 될 가능성이 높습니다.