프로그래머스 배달 (.Java)

public class delivery {

    static final int INF = 1000000;

    public static void main(String[] args) {
        Solution s = new Solution();
        int N = 5;
        int[][] road = { { 1, 2, 1 }, { 2, 3, 3 }, { 5, 2, 2 }, { 1, 4, 2 }, { 5, 3, 1 }, { 5, 4, 2 } };
        int K = 3;
        System.out.println(s.solution(N, road, K));
    }
}

class Solution {
    public int solution(int N, int[][] road, int K) {
       int[][] map = new int[N][N];                                      
	    
	    for (int i = 0; i < map.length; i++) {
	        for (int j = 0; j < map.length; j++) {
	            if (i == j) {                                               
	                map[i][j] = 0;    //배열 기준으로 자신의 자리를 0으로 만들어준다. 1번째 노드이면 배열 기준으로 [0,0]
	                continue;
	            }
	            map[i][j] = 500001;   //나머지는 거리를 구해야하기 때문에 최대값으로 바꾸어준다 만약 거리가 존재한다면 나중에 바꿔주고 거리가 존재하지 않는다면 500001로 그대로 두어진다.                                  
	        }
	    }

	    for (int i = 0; i < road.length; i++) {   //양방향 통행이기 때문에 왔다갈다 할때의 거리가 같이 때문에 값이 변하는 것을 2개 넣어준다.(단방향 x)
	        if(map[road[i][0] - 1][road[i][1] - 1] < road[i][2]) 
	        	continue;   
	        map[road[i][0] - 1][road[i][1] - 1] = road[i][2];                 //1 ex) 1번에서 2번으로 갈떄의 거리
        
	        map[road[i][1] - 1][road[i][0] - 1] = road[i][2];                 //2 ex) 2번에서 1번으로 갈떄의 거리
	    }
	    
	    for (int k = 0; k < N; k++) {                          //첫번째 노드부터 최적의 경로를 찾는다(연결된 모든 경로를 다 찾는다)             
	        for (int i = 0; i < N; i++) {                      
	            for (int j = 0; j < N; j++) {
	                if (map[i][j] > map[i][k] + map[k][j]) {
	                    map[i][j] = map[i][k] + map[k][j];
	                }
	            }
	        }
	    }

	    int count = 0;                                                      

	    for (int i = 0; i < map.length; i++) {      //경로를 다 찾으면 [0][i]번째 혹은 [i][0]번째 경로들이 싹 다오는데 거기서 k보다 작은 것들을 출력하면 된다.
	        if (map[0][i] <= K) 
	            count++;
	    }
	    
	    return count;
    }
}

 

출처 : [프로그래머스]배달 /Java (velog.io)