[JAVA 문제 풀이] 374. 배달

내가 작성한 코드

import java.util.*;

class Solution {
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        int[][] distance = new int[N + 1][N + 1]; // 마을 간의 거리 정보를 저장할 배열

        // 거리 배열 초기화
        for (int i = 1; i <= N; i++) {
            Arrays.fill(distance[i], Integer.MAX_VALUE);
            distance[i][i] = 0; // 자기 자신과의 거리는 0
        }

        // 도로 정보를 거리 배열에 반영
        for (int[] r : road) {
            int townA = r[0]; // 첫 번째 마을
            int townB = r[1]; // 두 번째 마을
            int AToBDis = r[2]; // 두 마을 간의 거리

            // 두 마을 간의 거리가 이미 존재하는 거리보다 짧으면 업데이트
            if (distance[townA][townB] > AToBDis) {
                distance[townA][townB] = AToBDis;
                distance[townB][townA] = AToBDis; // 양방향 도로이므로
            }
        }

        // 각 마을 간의 최단 거리 구하기 (
        for (int k = 1; k <= N; k++) { // 경유지 k
            for (int i = 1; i <= N; i++) { // 출발지 i
                for (int j = 1; j <= N; j++) {// 도착지 j
                    if (distance[i][k] != Integer.MAX_VALUE && distance[k][j] != Integer.MAX_VALUE) {
                        distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j]);
                    }
                }
            }
        }

        // 1번 마을에서 K 이하 거리인 마을 개수 세기
        for (int i = 1; i <= N; i++) {
            if (distance[1][i] <= K) {
                answer++;
            }
        }

        return answer;
    }
}

Floyd-Warshall Algorithm (플로이드-워셜 알고리즘) - stupefyee

기술정리

https://stupefyee.inblog.io/floydwarshall-algorithm-%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C%EC%9B%8C%EC%85%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98--62159?traffic_type=internal