[프로그래머스 Level.2] 배달 (Summer/Winter Coding(~2018)) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > Summer/Winter Coding(~2018) > 배달

 

 

 

문제 설명

 

 

N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 다음은 N = 5, K = 3인 경우의 예시입니다.

 

 

 

 

위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지는 3 이하의 시간에 배달할 수 있습니다. 그러나 3번 마을까지는 3시간 이내로 배달할 수 있는 경로가 없으므로 3번 마을에서는 주문을 받지 않습니다. 따라서 1번 마을에 있는 음식점이 배달 주문을 받을 수 있는 마을은 4개가 됩니다.

마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.

 

 

 

제한사항

 

• 마을의 개수 N은 1 이상 50 이하의 자연수입니다.
• road의 길이(도로 정보의 개수)는 1 이상 2,000 이하입니다.
• road의 각 원소는 마을을 연결하고 있는 각 도로의 정보를 나타냅니다.
• road는 길이가 3인 배열이며, 순서대로 (a, b, c)를 나타냅니다.
  • a, b(1 ≤ a, b ≤ N, a != b)는 도로가 연결하는 두 마을의 번호이며, c(1 ≤ c ≤ 10,000, c는 자연수)는 도로를 지나는데 걸리는 시간입니다.
  • 두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다.
  • 한 도로의 정보가 여러 번 중복해서 주어지지 않습니다.
• K는 음식 배달이 가능한 시간을 나타내며, 1 이상 500,000 이하입니다.
• 임의의 두 마을간에 항상 이동 가능한 경로가 존재합니다.
• 1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 return 하면 됩니다.

 

---

 

입출력 예

 

N	road	K	result
5	[[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]]	3	4
6	[[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]]	4	4

 

 

입출력 예 설명

 

입출력 예 #1

문제의 예시와 같습니다.

 

 

입출력 예 #2

주어진 마을과 도로의 모양은 아래 그림과 같습니다.

 

 

1번 마을에서 배달에 4시간 이하가 걸리는 마을은 [1, 2, 3, 5] 4개이므로 4를 return 합니다.

 

 

 

 

나의 코드

 

1. 플로이드 워셜(Floyd Warshall) 알고리즘 이용

class Solution {
    public int solution(int N, int[][] road, int K) {
        int answer = 0;

        int[][] dist = new int[N+1][N+1];
        
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(i == j)
                    dist[i][j] = 0;
                else
                    dist[i][j] = 1000000;
            }
        }
        
        for(int i=0; i<road.length; i++) {
            dist[road[i][0]][road[i][1]] = Math.min(dist[road[i][0]][road[i][1]], road[i][2]);
            dist[road[i][1]][road[i][0]] = Math.min(dist[road[i][1]][road[i][0]], road[i][2]);
        }
        
        for(int k=1; k<=N; k++) {
            for(int i=1; i<=N; i++) {
                for(int j=1; j<=N; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        
        for(int i=1; i<=N; i++) {
            if(dist[1][i] <= K) answer++;
        }
        
        return answer;
    }
}

 

풀이

1. 이 문제는 N개의 마을에서 1번 마을에서 시작해서 거리의 합이 K 이하인 마을을 모두 구하는 문제이다.
2. 그래프의 최단 경로를 구해 1번 마을에서 K 이하인 마을들을 구하는 것이기 때문에 플로이드 와샬(Floyd Warshall) 알고리즘 또는 다익스트라(Dijkstra) 알고리즘으로 풀면 된다.
3. 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이고 다익스트라 알고리즘은 하나의 정점에서 출발해서 거쳐가는 정점을 기준으로 모든 정점까지의 최단 경로를 구하는 알고리즘이다.
4. 플로이드 와샬 알고리즘 시작
5. 우선 모든 정점 사이의 거리를 저장 할 행과 열의 크기가 N+1인 2차원 배열 dist를 생성한다. 1번 접점부터 N번 접점까지를 그대로 나타내기 위해 N+1 크기로 생성한다.
6. dist를 1부터 N까지 이중 for문을 돌면서 접점에서 자기까지는 거리가 0이므로 0을 저장하고 나머지는 최대값(나올 수 없는 수)으로 초기화 하도록한다.
7. 그리고 주어진 road를 for문을 돌면서 dist[출발점][도착점] 에 Math.min()을 이용하여 현재 dist와 주어진 road의 해당 [출발점][도착점]의 값을 비교하여 저장한다.
8. 그리고 이제 1부터 N까지 3중 for문을 돌면서 최단 경로 길이를 업데이트하면 된다. 처음 for문을 거쳐가는 정점으로 잡고 두번째 for문을 출발점 세번째 for문을 도착점으로 하여 dist[출발점][도착점]에 Math.min()을 이용하여 현재 dist[출발점][도착점]과 dist[출발점][거쳐가는 정점] + dist[거쳐가는 정점][도착점]을 비교하여 최솟값으로 업데이트 해나가면 된다. 
9. 이렇게 모든 정점을 이용하여 3중 for문을 돌고나면 모든 정점 사이의 최단 경로 길이가 저장된다.
10. 문제는 1번 정점에서 모든 정점까지의 최단 경로가 K 이하인 것을 구하는 것이므로 dist[1][1]부터 dist[1][N]까지 중에 K 이하인 것들을 카운팅하여 리턴하면 된다.

 

 

2. 다익스트라(Dijkstra) 알고리즘 이용

import java.util.*;

class Solution {
    
    ArrayList<Node>[] graph;
    public int solution(int N, int[][] road, int K) {
        int answer = 0;

        graph = new ArrayList[N + 1];
        
        int[] dist = new int[N + 1];
        
        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]));
        }
        
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        dijkstra(1, dist);
        
        for(int i=1; i<dist.length; i++) {
            if(dist[i] <= K) answer++;
        }
        
        return answer;
    }
    
    public void dijkstra(int start, int[] dist) {
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        pq.add(new Node(start, 0));
        dist[start] = 0;
        
        while(!pq.isEmpty()) {
            Node nowNode = pq.poll();
            int nIdx = nowNode.idx;
            int nCost = nowNode.cost;
            
            if(nCost > dist[nIdx]) continue;
            
            ArrayList<Node> nodeList = graph[nIdx];
            for(Node node : nodeList) {
                int cost = dist[nIdx] + node.cost;

                if(cost < dist[node.idx]) {
                    dist[node.idx] = cost;
                    pq.offer(new Node(node.idx, cost));
                }
            }
        }
    }
    
    class Node {
        int idx;
        int cost;
        
        Node(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }
    }
    
}

 

풀이

1. 이 문제는 N개의 마을에서 1번 마을에서 시작해서 거리의 합이 K 이하인 마을을 모두 구하는 문제이다.
2. 그래프의 최단 경로를 구해 1번 마을에서 K 이하인 마을들을 구하는 것이기 때문에 플로이드 와샬(Floyd Warshall) 알고리즘 또는 다익스트라(Dijkstra) 알고리즘으로 풀면 된다.
3. 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이고 다익스트라 알고리즘은 하나의 정점에서 출발해서 거쳐가는 정점을 기준으로 모든 정점까지의 최단 경로를 구하는 알고리즘이다.
4. 다익스트라 알고리즘 시작
5. 한 정점에서 정점까지의 거리를 객체로 저장하기 위해 정점(idx)과 걸리는 시간(cost)을 갖는 Node 클래스를 생성한다.
6. 이 Node 객체를 선언 타입으로 하는 ArrayList를 타입으로 하는 배열 graph를 N+1 크기로 생성한다. 정점이 1부터 N까지 있으므로 N+1 크기로 생성한다.
7. 1번정점에서 해당 정점까지의 거리를 저장 할 int 타입 배열 dist를 마찬가지로 N+1 크기로 생성하고 dist를 Arrays.fill()을 이용하여 최대값(나올 수 없는 수)으로 초기화 한다.
8. 배열 graph를 1부터 N까지 돌면서 해당 인덱스에  ArrayList를 생성한다.
9. 이제 주어진 road를 for문을 돌면서 배열 graph[출발점]의 ArrayList에 Node(도착점, 걸리는 시간 값)을 생성하여 add()를 이용해 넣어주도록 한다.
10. 그리고 dijkstra(출발점, dist)를 호출한다.
11. dijkstra()에서는 Node를 선언 타입으로 하고 cost를 기준으로 오름차순으로 정렬하는 우선순위큐를 생성하고 Node(start, 0)을 생성하여 add()를 이용해 담는다. 출발점 1에서 1(출발했던 정점)까지 걸리는 시간은 0이므로 Node(start, 0)을 생성해 우선순위큐에 담은 것이다.
12. 그리고 dist[출발점]을 0으로 저장하고 우선순위큐가 빌 때까지 while 반복문을 실행한다.
13. while 반복문에서는 poll()을 이용하여 pq에서 제일 우선순위 높은 Node를 꺼내고 해당 Node의 정점인 idx와 해당 Node까지 걸리는 시간인 cost를 nIdx와 nCost로 저장한다.
14. 우선순위큐에서 꺼낸 해당 정점까지의 최소 걸리는 시간 nCost가 현재 해당 정점까지 최소 걸리는 시간으로 저장된 dist[nIdx] 보다 크면 볼 필요가 없으니 coninue를 이용하여 넘어간다.
15. 그게 아니라면 road를 이용하여 배열 graph[nIdx]에 저장했던 ArrayList를 for each문을 돌면서 ArrayList에서 Node를 꺼낸다. 꺼낸 Node에서 해당 정점까지 걸리는 시간과 dist[nIdx]를 더해 int형 변수 cost에 저장한다.
16. cost가 꺼낸 Node의 idx를 인덱스로 하는 dist보다 작으면 해당 dist에 cost를 저장하고 우선순위큐에 Node(해당 idx, cost)를 생성하여 담아준다.
17. 즉, 걸리는 시간이 작은 것이 우선순위가 높도록 우선순위큐를 생성하고 처음에 시작 정점과 걸리는 시간 0인 Node를 담고 dist[시작점]을 0으로 저장하고 시작한다. 우선순위큐에서 걸리는 시간이 작은 Node를 선택하여 꺼내고 dist와 비교하여 최소 걸리는 시간이 아니면(dist보다 크다면) 넘어간다. 최소 걸리는 시간이라면(dist와 같거나 작다면) 이 정점의 인접한 정점들을 선택하여 이 정점들을 인접 정점으로 거쳐서 갈 때 걸리는 시간을 구하고 기존의 최소 걸리는 시간보다 더 작게 걸린다면(dist보다 더 작다면) 업데이트 하는 것이다.
18. 이렇게 1번 정점으로부터 모든 정점까지의 최소 걸리는 시간을 구하고 나서 dist[1]부터 dist[N]까지 중에 K 이하인 것들을 카운팅하여 리턴하면 된다.

 

 

 

 

결과

플로이드 워셜(Floyd Warshall) 알고리즘 이용	다익스트라(Dijkstra) 알고리즘 이용