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

• 배달

풀이과정

• 참고 - 다익스트라 알고리즘

1. 각각의 마을에서 다른 마을로의 이동시간을 나타내는 grid를 만든다.
   이 때 중간에 다른 마을을 거치는 경우는 고려하지 않는다. 문제에서 주어진 예제 1번의 경우에는 아래의 그림과 같이 표현된다.
   

   

   • 문제 조건에 의해 배달을 출발하는 마을은 1번 마을로 고정되어 있으므로 1번 마을에서 출발하여 1번 마을로 도착하는 경우 걸리는 시간을 0으로 설정한다.
   • 1번 마을을 이미 방문했음을 표시한다.
2. 아직 방문하지 않은 마을들 중 현재 마을(최초 시작시에는 1번 마을)에서 최단 시간에 이동할 수 있는 마을로 이동한다.
   위의 예시에서는 2번과 4번 마을로 이동이 가능하지만 2번 마을이 소요시간 1로 가장 작으므로 2번 마을로 이동하게 된다.
   • 이동한 마을을 방문했음을 표시한다. 예시에서는 2번 마을을 방문했음을 표시하게 된다.
3. 과정 2에서 이동한 현재 마을 (예시에서는 2번 마을)에서 이동할 수 있는 마을들을 모두 찾는다.
   • 위 예시의 경우에는 1번, 3번, 5번 마을이 해당된다.
   • 각각의 마을에 대해 1번 마을에서 바로 이동하는 경우와, 현재 마을을 거쳐 이동하는 경우 중 소요시간이 작은 쪽을
     기록한다. 위의 예시에 대해서는 아래의 그림과 같이 표현된다.
     

     

   • 1 -> 2 -> 1 이동시간은 1 + 1 = 2 이고, 1 -> 1 이동시간은 0 이므로 값은 그대로 0
   • 1 -> 2 -> 3 이동시간은 1 + 3 = 4 이고, 1 -> 3 이동시간은 inf 이므로 3번 마을로의 이동시간을 4로 업데이트한다.
   • 1 -> 2 -> 5 이동시간은 1 + 2 = 3 이고, 1 -> 5 이동시간은 inf이므로 5번 마을로의 이동시간을 3으로 업데이트한다.
4. 주어진 문제 조건에 의해 임의의 두 마을은 반드시 연결되어 있다 하였으므로, 전체 마을을 모두 방문할 때 까지 과정 2번과 3번을 반복한다. 모든 반복이 종료되면 index가 0인 row에는 1번 마을에서 다른 마을로 도착할 때 까지 소요되는 시간들이 모두 저장되어 있다. 이 값들 중 K 이하인 값들의 수를 세어 반환한다.

Code

import java.util.*;

class Solution {
    final int inf = Integer.MAX_VALUE;

    public int solution(int N, int[][] roads, int K) {
        int[][] towns = new int[N][N];
        for (int[] town : towns) {
            Arrays.fill(town, inf);
        }
        towns[0][0] = 0; // 1번 마을은 무조건 배달 가능!

        for (int[] road : roads) {
            towns[road[0] - 1][road[1] - 1] = Math.min(towns[road[0] - 1][road[1] - 1], road[2]);
            towns[road[1] - 1][road[0] - 1] = towns[road[0] - 1][road[1] - 1];
        }

        Set<Integer> visited = new HashSet<>();
        visited.add(0); // starting point

        while (visited.size() < N) {
            int visitTarget = getNextVisit(towns[0], visited);
            visited.add(visitTarget);

            int[] visitable = towns[visitTarget];
            for (int i = 0; i < visitable.length; i++) {
                if (visitable[i] < inf) {
                    towns[0][i] = Math.min(towns[0][i], towns[0][visitTarget] + visitable[i]);
                }
            }
        }

        int count = 0;
        for (int i = 0; i < N; i++) {
            if (towns[0][i] <= K) {
                count++;
            }
        }

        return count;
    }

    private int getNextVisit(int[] distances, Set<Integer> visited) {
        int idx = 0;
        int min = inf;

        for (int i = 0; i < distances.length; i++) {
            if (distances[i] < min && !visited.contains(i)) {
                idx = i;
                min = distances[i];
            }
        }

        return idx;
    }
}

결과