[프로그래머스] 배달

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

코딩테스트 연습 - 배달

 

이 문제는 처음에 dfs로 시도를 했으나... 생각보다 실패가 많았다... 그러던 중 플로이드 와샬(Floyd Warshall) 알고리즘이라는 것을 알게되었다.

 

최단 거리를 구하는 알고리즘으로 start에서 end까지 바로 가는 경로와 (start에서 K(지나가는 어떤 점)까지의 거리 + K부터 end까지 거리) 경로 중 더 짧은 거리를 구하는 방식이다.

 

2차원 배열을 통해서 구현할 수 있으며, 이 문제에서는 출발점이 1번 마을이었기 때문에 최단 거리를 구한 뒤, row가 1인 행에서 시간 내 배달이 가능한 열의 수를 구하면 된다.

 

코드는 다음과 같다.

class Solution {
    public int solution(int N, int[][] road, int K) {
        int[][] distance = new int[N + 1][N + 1];
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                if(i == j) continue;
                distance[i][j] = 500001;
            }
        }

        for (int[] r : road) {
            distance[r[0]][r[1]] = Math.min(distance[r[0]][r[1]], r[2]);
            distance[r[1]][r[0]] = Math.min(distance[r[1]][r[0]], r[2]);
        }

        // k: 거쳐가는 어떤 지점
        for (int k = 1; k <= N; k++) {
            // i : 시작점
            for (int i = 1; i <= N; i++) {
                // j : 도착점
                for (int j = 1; j <= N; j++) {
                    distance[i][j] = Math.min(distance[i][k] + distance[k][j], distance[i][j]);
                }
            }
        }

        int answer = 1;
        for (int i = 1; i <= N; i++) {
            if (distance[1][i] > 0 && distance[1][i] <= K) answer++;
        }

        return answer;
    }
}

 

참고

• https://pangsblog.tistory.com/90