[프로그래머스][JAVA]Lv. 2 - 배달

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

프로그래머스

오랜만에 푸는 문제..

1번 마을에서 다른 마을에 최소 비용(K이하)로 갈 수 있을 경우 answer 증가

최소 비용 문제이므로, 다익스트라 또는 플로이드 워셜을 사용하여 문제를 풀어야할듯

때문에 여기서는 플로이드 워셜을 사용하여 문제 해결.

class Solution {
    public int solution(int N, int[][] road, int K) {
        int answer = 1; // 시작 지점인 1을 포함
        int[][] area = new int[N+1][N+1];

        for(int i = 0; i <= N; i++) {
            for(int j = 0; j <= N; j++) {
                if(i == j) area[i][j] = 0;
                else area[i][j] = 10000000;
            }
        } // 배열 초기화

        for (int[] ints : road) {
            int s = ints[0];
            int e = ints[1];
            int v = ints[2];
            if (area[s][e] > v) area[s][e] = v;
            s = ints[1];
            e = ints[0];
            v = ints[2];
            if (area[s][e] > v) area[s][e] = v;
        } // 그래프를 양 방향으로 만듬
        
        for(int k = 0; k <= N; k++) {
            for(int i = 0; i <= N; i++) {
                for(int j = 0; j <= N; j++) {
                    if(area[i][j] > area[i][k] + area[k][j])
                        area[i][j] = area[i][k] + area[k][j];
                }
            }
        } // 플로이드 워셜
        
        for(int i = 0; i < area[1].length; i++) {
            if(area[1][i] != 0 && area[1][i] <= K) answer++;
        }

        return answer;
    }
}