[프로그래머스 Summer/Winter Coding(~2018)] 배달 -Java

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

코딩테스트 연습 - 배달

class Solution {
	    public int solution(int N, int[][] road, int K) {
	        int answer = 0;
	        
	        int [][]map=new int[N+1][N+1];
	        
	        for(int i=0; i<road.length; i++) {
	        	int start=road[i][0];
	        	int end=road[i][1];
	        	int cost=road[i][2];
	        	
	        	if(map[start][end]==0) map[start][end]=cost;
	        	else map[start][end]=Math.min(map[start][end], cost);
	        	
	        	if(map[end][start]==0) map[end][start]=cost;
	        	else map[end][start]=Math.min(map[end][start], cost);
	        }
	        
	        for(int k=1; k<=N; k++) {
	        	for(int i=1; i<=N; i++) {
	        		for(int j=1; j<=N; j++) {
	        			if(map[i][k]==0 || map[k][j]==0 || i==j) continue;
	        			if(map[i][k]+map[k][j]<map[i][j]) map[i][j]=map[i][k]+map[k][j];
	        			if(map[i][j]==0) map[i][j]=map[i][k]+map[k][j];
	        		}
	        	}
	        }
	        
	        for(int i=1; i<=N; i++) {
	        	if(map[1][i]<=K) answer++;
	        }
	        
	        
	        //플루이드 - 와샬
	        


	        return answer;
	    }
	    
	}

소요시간 : 20분

 

플루이드 와샬 알고리즘을 사용했습니다.

마을의 수도 작았기 때문에 3중 포문을 써도 충분하게 통과할 것이라고 생각했습니다.

 

처음 입력받을 때 같은 출발지에서 같은 도착지로의 여러 개의 입력이 들어올 수 있기 때문에 

작은 입력값으로 교체해야 합니다.

 

그리고 3중포문 (k : 경유지  i : 출발지  j : 도착지)에 대해서 플루이드 와샬을 돌렸습니다~