[c++][java][프로그래머스] 배달

프로그래머스 배달 [Summer/Winter Coding(~2018)]
https://programmers.co.kr/learn/courses/30/lessons/12978?language=java

코딩테스트 연습 - 배달

문제 풀이

• 이 문제는 1번 마을을 기준으로 모든 마을의 거리를 구한 후 거리가 K 이하인 마을의 개수를 return 하면 됩니다.
• 1번 마을에서 다른 모든 마을의 거리를 구하기 위해 Single Source Shortest Path 알고리즘인 다익스트라(Dijkstra) 알고리즘을 사용했습니다. 
• "두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다."라는 제한사항이 있기 때문에, graph를 초기화할 때 min을 사용했습니다. (항상 최단 경로로 다닐 것이기 때문,,)

코드 (c++)

#include <vector>
#include <queue>

using namespace std;

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    
    vector<vector<int>> graph(N+1, vector<int>(N+1, 1e8));
    for(int i=1; i<=N; ++i) graph[i][i] = 0;
    
    for(auto r: road) {
    	// 제한사항 때문에 min 사용
        graph[r[0]][r[1]] = min(graph[r[0]][r[1]], r[2]);
        graph[r[1]][r[0]] = min(graph[r[1]][r[0]], r[2]);
    }
    
    // Dijkstra Algorithm
    priority_queue<pair<int,int>> pq; // dist, index
    vector<int> dist(N+1, 1e8);
    
    pq.push({0, 1});
    dist[1] = 0;
    
    while(!pq.empty()) {
        int d = -pq.top().first;
        int node = pq.top().second;
        pq.pop();
        
        for(int i=1; i<=N; ++i) {
            if(i == node || graph[node][i] == 1e8) continue;
            
            if(dist[i] > d + graph[node][i]) {
                dist[i] = d + graph[node][i];
                
                pq.push({-dist[i], i});
            }
        }
    }

    for(int i=1; i<=N; ++i) {
        if(dist[i] <= K) answer++;
    }
    
    return answer;
}

실행 결과 (c++)

 

코드 (Java)

import java.util.*;

class Solution {
    
    static final int MAX = (int) 1e8;
    
    static class Pair implements Comparable<Pair> {
        int first;
        int second;

        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }

        @Override
        public int compareTo(Pair o) {
            return Integer.compare(this.first, o.first);
        }
    }
    
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        
        int[][] graph = new int[N+1][N+1];
        for(int i=1; i<=N; ++i) {
            Arrays.fill(graph[i], MAX);
            graph[i][i] = 0;
        }
        
        for(int[] r: road) {
            graph[r[0]][r[1]] = Integer.min(graph[r[0]][r[1]], r[2]);
            graph[r[1]][r[0]] = Integer.min(graph[r[1]][r[0]], r[2]);
        }
        
        int[] dist = new int[N+1];
        Arrays.fill(dist, MAX);
        PriorityQueue<Pair> pq = new PriorityQueue<>();
        
        pq.add(new Pair(0, 1));
        dist[1] = 0;
        
        while(!pq.isEmpty()) {
            int d = pq.peek().first;
            int node = pq.peek().second;
            pq.remove();
            
            for(int i=1; i<=N; ++i) {
                if(i == node || graph[node][i] == MAX) continue;
                
                if(dist[i] > d + graph[node][i]) {
                    dist[i] = d + graph[node][i];
                    
                    pq.add(new Pair(dist[i], i));
                }
            }
        }
        
        answer = (int) Arrays.stream(dist).filter(num -> num <= K).count();      
        
        return answer;
    }
}

실행 결과 (Java)