[프로그래머스] 배달(12978)

1. 문제 풀이 아이디어

• 플로이드 워셜 알고리즘을 활용하여 문제를 해결할 수 있다.

2. 나의 정답 코드

class Solution {
    public int solution(int N, int[][] road, int K) {
        int answer = 1;
        int[][] graph = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                graph[i][j] = 500001;
            }
        }
        for (int i = 0; i < road.length; i++) {
            graph[road[i][0]][road[i][1]] = Math.min(graph[road[i][0]][road[i][1]], road[i][2]);
            graph[road[i][1]][road[i][0]] = Math.min(graph[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++) {
                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }
        for (int i = 2; i <= N; i++) {
            if (graph[1][i] <= K) answer++;
        }
        return answer;
    }
}

3. 정리

• 그래프 배열을 초기화할 때, 문제의 최대값인 500001로 채운다.

• 입력값을 처리하며 graph 배열에서 경로의 값을 갱신한다.

• 플로이드 워셜 알고리즘을 사용하여 배열에서 각 경로의 최소값을 갱신한다.

• answer는 1번 마을을 포함하여 1로 초기화한다.

• 2번 마을부터 N번 마을까지 순회하며, 1번 마을에서 해당 마을까지의 경로가 K 이하일 경우 answer를 증가시킨다.