[Programmers] LV2 - 배달

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

코딩테스트 연습 - 배달

 

문제 파악

문제의 그림에서 주어졌듯이, 그래프로써 문제를 풀어나가야 한다는 것을 유추할 수 있다.

또한, 문제를 읽다 보면 "각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다."라는 구문이 있다.

그래서 처음에는 "무방향 + 그래프" => 플로이드-와샬 알고리즘을 선택했다.

 

class Solution {
    static final int INF = Integer.MAX_VALUE / 2;
    public int solution(int N, int[][] road, int K) {
        int answer = 1;

        int[][] adj = new int[N+1][N+1];

        for(int r = 0; r<=N;r++)
        {
            for(int c = 0; c<=N;c++)
            {
                adj[r][c] = r == c ? 0 :INF;
            }
        }

        for(int idx = 0; idx<road.length;idx++)
        {
            int r = road[idx][0];
            int c = road[idx][1];
            int p = road[idx][2];
            
            int min = Math.min(adj[r][c], p);
            
            adj[r][c] = adj[c][r] = min;
        }

        for(int t = 1; t<=N;t++)
        {
            for(int s = 1; s<=N;s++)
            {
                if(t == s) continue;

                for(int e = 1; e<=N;e++){
                    if(s == e) continue;

                    adj[s][e] = Math.min(adj[s][e],(adj[s][t]+adj[t][e]));
                }
            }
        }

        for(int r = 1; r<2;r++)
        {
            for(int c = r+1; c<=N;c++)
            {
                if(adj[r][c]<=K){
                    answer++;
                }
            }
        }

        return answer;
    }
}

 

먼저 플로이드-와샬 알고리즘으로 통과하였고 예제 2번을 보아하니 다익스트라 알고리즘으로도 해결할 수 있을 거 같아 우선순위 큐를 활용한 다익스트라 알고리즘으로도 해결해 보았다.

 

import java.util.*;
class Solution {
    static final int INF = Integer.MAX_VALUE / 2;
   public int solution(int N, int[][] road, int K) {

        int answer = 0;

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        ArrayList<ArrayList<Edge>> adj = new ArrayList<>();
        int[] dist = new int[N+1];

        Arrays.fill(dist,INF);

        for(int idx = 0; idx<=N;idx++){
            adj.add(new ArrayList<>());
        }

        for(int idx = 0; idx<road.length;idx++)
        {
            int s = road[idx][0];
            int e = road[idx][1];
            int w = road[idx][2];

            adj.get(s).add(new Edge(e,w));
            adj.get(e).add(new Edge(s,w));
        }

        dist[1] = 0;
        pq.offer(new Edge(1,0));

        while(!pq.isEmpty()){
            Edge e = pq.poll();
            for(Edge edge : adj.get(e.to)){
                if(dist[edge.to] > dist[e.to]+edge.weight){
                    dist[edge.to] = dist[e.to]+edge.weight;
                    pq.offer(edge);
                }
            }
        }

        for(int weight : dist){
            if(weight <=K){
                answer++;
            }
        }
        return answer;
    }

    class Edge implements Comparable<Edge>{
        int to, weight;

        Edge(int to , int weight){
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge e){
            return this.weight - e.weight;
        }
    }
}

 

우선순위 큐 + 다익스트라 알고리즘으로 해결한 코드는 

아래 분의 블로그를 참조하였다.

참조 사이트 : https://gomgomkim.tistory.com/19