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

알고리즘 문제 풀이 / 프로그래머스 (programmers)  -  배달

 

문제 링크

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

코딩테스트 연습 - 배달

문제 풀이

public class delivery {
	public static int solution(int N, int[][] road, int K) {
    
		int answer = 0;
		int[][] order = new int[N][N];

		for(int i = 0; i < road.length; i++) {
			int a = road[i][0]-1;
			int b = road[i][1]-1;
		
			if(order[a][b] != 0 ) {
				order[a][b] =road[i][2] < order[a][b] ? road[i][2] : order[a][b];
				order[b][a] =road[i][2] < order[b][a] ? road[i][2] : order[b][a];
			}else {
				order[a][b] = road[i][2];
				order[b][a] = road[i][2];
			}
		}

		int distance[] = new int[N];
		boolean visit[] = new boolean[N];

		for(int i = 0; i < N; i++)
			distance[i] = Integer.MAX_VALUE;

		distance[0] = 0;
		visit[0] = true;

		for(int i = 0; i < N; i++) {
			if(!visit[i] && order[0][i] != 0)
				distance[i] = order[0][i];
		}

		for(int a = 0; a < N-1; a++) {
			int min_distance = Integer.MAX_VALUE;
			int min_index = 0;

			for(int i = 0; i < N; i++) {
				if(!visit[i]  && min_distance > distance[i]) {
					min_distance = distance[i];
					min_index = i;
				}
			}
            
			visit[min_index] = true;
			for(int i = 0; i < N; i++) {
				if(!visit[i] && order[min_index][i] != 0) {				
					if(distance[i] > distance[min_index] + order[min_index][i])
						distance[i] = distance[min_index] + order[min_index][i];
				}
			}
		}

		for(int i = 0; i < distance.length; i++) {
			if(distance[i] <= K)
				answer++;
		}
        
		return answer;
	}
}

 

- 한 노드로 가는 거리가 두개 이상인 경우는 애초에 배열에 넣을 때 최단거리로 갱신해줬다.

- 다익스트라를 활용하여 각 노드까지의 최단거리를 distance 배열에 넣어줬다.

- distance 값들 중 배달 가능한 지역 K 값 이하의 지역(노드)이 답이므로 answer을 증가 시켜준다