Java 프로그래머스 배달

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

프로그래머스

문제 분류 : 코딩테스트 연습 > Summer/Winter Coding(~2018)  > 배달

난이도 : 2

 

문제 풀이1 (정답 코드)

다익스트라를 사용해서 풀었다.

근데 문제를 풀고 생각해 보니 한 번만 다익스트라를 돌려도 1에서 각 마을로 가는 최단거리는 모두 구했으니

메서드로 마을마다 매번 구할 필요가 없구나를 깨달았다. (문제 풀이2에 적용)

import java.util.*;
class Solution {
    static class node{
        int v; int value;
        public node(int v, int value){
            this.v = v; this.value = value;
        }
    }
    static ArrayList<node>[] graph;
    static int limit; 
    static int answer;
    static int m;
    static final int INF = 10000 * 2000 + 1;
    
    public int solution(int N, int[][] road, int K) {
        answer = 0;
        graph = new ArrayList[N+1];
        for(int i = 0; i <= N; i++){
            graph[i] = new ArrayList<>();
        }
        // 간선의 정보 
        for(int i = 0; i < road.length; i++){
            int start = road[i][0];
            int end   = road[i][1];
            int value = road[i][2];
            graph[start].add(new node(end, value));
            graph[end].add(new node(start, value));
        }
        limit = K;
        m = N;
        for(int i = 2; i <= N; i++){
            dijkstra(i);
        }
        return answer + 1;
    }
    public static void dijkstra(int end){
        int [] memo = new int [m+1];
        Arrays.fill(memo, INF);
        memo[1] = 0;
        PriorityQueue<node> pq = new PriorityQueue<>((o1,o2)->o1.value-o2.value);
        pq.add(new node(1, 0));
        while(!pq.isEmpty()){
            node node = pq.poll();
            if(memo[node.v]!=node.value) continue;
            for(node next : graph[node.v]){
                if(memo[next.v] <= memo[node.v] + next.value) continue;
                memo[next.v] = memo[node.v] + next.value;
                pq.add(new node(next.v, memo[next.v]));
            }
        }
        if(memo[end] <= limit) answer++;
    }
}

문제 풀이2  (정답 코드)

다익스트라를 한 번만 돌려서 해결

import java.util.*;
class Solution {
    static class node{
        int v; int value;
        public node(int v, int value){
            this.v = v; this.value = value;
        }
    }
    static ArrayList<node>[] graph;
    
    static int limit; 
    static int answer;
    static int m;
    static final int INF = 10000 * 2000 + 1;
    
    public int solution(int N, int[][] road, int K) {
        answer = 0;
        graph = new ArrayList[N+1];
        for(int i = 0; i <= N; i++){
            graph[i] = new ArrayList<>();
        }
        // 간선의 정보 
        for(int i = 0; i < road.length; i++){
            int start = road[i][0];
            int end   = road[i][1];
            int value = road[i][2];
            graph[start].add(new node(end, value));
            graph[end].add(new node(start, value));
        }
        limit = K;
        m = N;
        int [] memo = new int [m+1];
        Arrays.fill(memo, INF);
        memo[1] = 0;
        PriorityQueue<node> pq = new PriorityQueue<>((o1,o2)->o1.value-o2.value);
        pq.add(new node(1, 0));
        while(!pq.isEmpty()){
            node node = pq.poll();
            if(memo[node.v]!=node.value) continue;
            for(node next : graph[node.v]){
                if(memo[next.v] <= memo[node.v] + next.value) continue;
                memo[next.v] = memo[node.v] + next.value;
                pq.add(new node(next.v, memo[next.v]));
            }
        }
        for(int i = 2; i <= N; i++){
            if(memo[i] <= limit) answer++;
        }
        return answer + 1;
    }
}

문제 풀이3 (정답 코드)

플로이드 알고리즘 적용 

import java.util.*;
class Solution {
    static final int INF = 10000 * 2000 + 1;
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        int [][] memo = new int [N+1][N+1];
        for(int i = 0; i <= N; i++){
            for(int j = 0; j <= N; j++){
                if(i != j) memo[i][j] = INF;
            }
        }
        // 간선의 정보 
        for(int i = 0; i < road.length; i++){
            int start = road[i][0];
            int end   = road[i][1];
            int value = road[i][2];
            memo[start][end] = Math.min(memo[start][end], value);
            memo[end][start] = Math.min(memo[end][start], value);
        }
        // 플로이드 알고리즘 적용
        for(int k = 1; k <= N; k++){
            for(int i = 1; i <= N; i++){
                for(int j = 1; j <= N; j++){
                    memo[i][j] = Math.min(memo[i][j], memo[i][k] + memo[k][j]);
                }
            }
        }
        for(int i = 1; i <= N; i++){
            if(memo[1][i] <= K) answer++;
        }
        return answer;
        
    }
}