[ JAVA ] 프로그래머스 - 배달

https://programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

[ 풀이 ]

최단 경로? 노드와 그래프? 문제를 읽고나서 떠오른 것이 바로 다익스트라 알고리즘이었다. 그리고 다익스트라 알고리즘을 적용하여 풀어보니 바로 테스트 합격이 떴다. 

 

[ 1 . 그래프, 최단거리 초기화 ] 

각 노드에 인접한 노드들에 대한 정보( 마을번호 , 배달 시간 )를 담은 배열 graph[]를 생성한다.

그리고 1번 마을에서부터 각 마을까지의 최단 배달시간에 대한 정보를 담은 배열 dist[]을 생성한다.

class Solution {
    static ArrayList<Node>[] graph; // 각 노드에 인접한 노드들에 대한 정보를 담은 리스트
    static int[] dist;  // 1번도시와 다른 도시간 최단 경로
    public int solution(int N, int[][] road, int K) {
        // N : 마을 개수 , road : 마을 번호와 비용 , K : 기준 시간
        int answer = 0;
        
        // 초기화 과정 시작
        graph = new ArrayList[ N + 1 ];
        dist = new int[ N + 1 ];
        Arrays.fill( dist , Integer.MAX_VALUE );
        for( int i = 1 ; i <= N ; i++ ){
            graph[i] = new ArrayList<>();
        }
        for( int i = 0 ; i < road.length ; i++ ){
            graph[ road[i][0] ].add( new Node( road[i][1] , road[i][2] ) );
            graph[ road[i][1] ].add( new Node( road[i][0] , road[i][2] ) );
        }
        dist[1] = 0;    // 1번마을에서 자신까지는 거리가 0임
        // 초기화 과정 끝

        return answer;
    }
}

[ 2 . 다익스트라 ]

public void dijkstra(){
    PriorityQueue<Node> queue = new PriorityQueue<>( (o1,o2) -> {
       return o1.cost - o2.cost; // 최단비용(경로)으로 우선순위를 둠
    });
    queue.add( new Node( 1 , 0 ) );
    while( !queue.isEmpty() ){
        Node node = queue.poll();
        int curIdx = node.idx;
        int curCost = node.cost;
        if( dist[curIdx] < curCost ) continue;

        // 해당 도시와 연결된 모든 도시들을 탐색
        for( int i = 0 ; i < graph[curIdx].size() ; i++ ){  
            int nextIdx = graph[curIdx].get(i).idx;
            int nextCost = graph[curIdx].get(i).cost + curCost ;

            // 최단경로인지 확인, 맞으면 dist 다시 세팅 후 다음 경로 파악
            if( dist[nextIdx] > nextCost ){ 
                dist[nextIdx] = nextCost;
                queue.add( new Node( nextIdx , nextCost ) );
            }
        }
    }
}
class Node{
    int idx;    // 노드 번호
    int cost;   // 가중치( 시간 )
    Node( int idx , int cost ){
        this.idx = idx;
        this.cost = cost;
    }
}

 

[ 전체 코드 ]

import java.util.*;
class Solution {
    static ArrayList<Node>[] graph; // 각 노드에 인접한 노드들에 대한 정보를 담은 리스트
    static int[] dist;  // 1번도시와 다른 도시간 최단 경로
    public int solution(int N, int[][] road, int K) {
        // N : 마을 개수 , road : 마을 번호와 비용 , K : 기준 시간
        int answer = 0;
        
        // 초기화 과정 시작
        graph = new ArrayList[ N + 1 ];
        dist = new int[ N + 1 ];
        Arrays.fill( dist , Integer.MAX_VALUE );
        for( int i = 1 ; i <= N ; i++ ){
            graph[i] = new ArrayList<>();
        }
        for( int i = 0 ; i < road.length ; i++ ){
            graph[ road[i][0] ].add( new Node( road[i][1] , road[i][2] ) );
            graph[ road[i][1] ].add( new Node( road[i][0] , road[i][2] ) );
        }
        dist[1] = 0;    // 1번마을에서 자신까지는 거리가 0임
        // 초기화 과정 끝
        
        dijkstra(); // 다익스트라 
    	
        // 각각의 최단거리가 배달가능시간인지 확인
        for( int i = 1 ; i < dist.length ; i++ ){
            if( dist[i] <= K ) answer++;
        }        
        return answer;
    }
    public void dijkstra(){
        PriorityQueue<Node> queue = new PriorityQueue<>( (o1,o2) -> {
           return o1.cost - o2.cost; // 최단비용(경로)으로 우선순위를 둠
        });
        queue.add( new Node( 1 , 0 ) );
        while( !queue.isEmpty() ){
            Node node = queue.poll();
            int curIdx = node.idx;
            int curCost = node.cost;
            if( dist[curIdx] < curCost ) continue;
            
            // 해당 도시와 연결된 모든 도시들을 탐색
            for( int i = 0 ; i < graph[curIdx].size() ; i++ ){  
                int nextIdx = graph[curIdx].get(i).idx;
                int nextCost = graph[curIdx].get(i).cost + curCost ;
                
                // 최단경로인지 확인, 맞으면 dist 다시 세팅 후 다음 경로 파악
                if( dist[nextIdx] > nextCost ){ 
                    dist[nextIdx] = nextCost;
                    queue.add( new Node( nextIdx , nextCost ) );
                }
            }
        }
    }
    class Node{
        int idx;    // 노드 번호
        int cost;   // 가중치( 시간 )
        Node( int idx , int cost ){
            this.idx = idx;
            this.cost = cost;
        }
    }
}