[프로그래머스,Java] Level2: 배달

문제분석

 

문제로, 각 마을간의 다리와 이동거리를 주어집니다.  

 

목표 : 1번마을로부터 출발한다고 가정할때, N시간 이하로 배달이 완료되는 지역 개수를 구하시오.

 

요점은, 정점과 정점 사이의 최소거리를 구하는 알고리즘을 구현하면된다.

 

그게 바로, 플로이드 와샬 알고리즘이다.

 

구현은 구글링을하시면 다 나와있습니다.

 

플로이드 와샬 구현법: 

 

1. 정점의 개수만큼 2차원 배열 생성,  그리고 모든 배열값에 INF 부여 (큰 숫자)

 

2. 입력으로 받은 정점과 정점사이의 다리를 입력합니다.

 

3. 3차반복을통해,  정점과 정점사이의 다리의 최소거리를 구합니다.

 

사실 이 플로이드 와샬 알고리즘은 꽤나 쉽게 구현이 가능합니다.

 

자세하게 돌아가는 원리를 아는게 힘들다면, 언제 어떨때 써야하는지 알고,  검색하고 적용하는게 중요하다고 봅니다.

 

 

문제풀이

 

import java.util.*;
class Solution {
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        int[][] map =new int[N][N];
        
        //모든 map값의 INF값을 넣는다.(플로이드 와샬 쓰기위해) map[정점][정점]은 0으로초기화
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                if (i == j){                                  
                    continue;
                }
                map[i][j] = 500001;  
            }
        }
        // 정점과 정점을 연결해주는 맵을 그린다. 
        for(int[] data:road){
            //새로운 다리가 기존에 있던 다리보다 크면 넘긴다. 작으면 갱신한다. 
            if(map[data[0]-1][data[1]-1]<data[2]){
                continue;
            }
            map[data[0]-1][data[1]-1]=data[2];
            map[data[1]-1][data[0]-1]=data[2];
        }
        //플로이드 와샬 : 정점과 정점 사이의 최소거리를 구해주는 알고리즘
        for(int i=0; i<map.length; i++) {
            for(int j=0; j<map.length; j++) {
                for(int k=0; k<map.length; k++) {
                    if(map[j][k] > map[j][i] + map[i][k])
                        map[j][k] = map[j][i] + map[i][k];
                }
            }
        }
        // 1번 마을부터 출발하니, map[0]를 순환한다. 시간이 K이하면 answer++
        for (int i = 0; i < map[0].length; i++) {
            if (map[0][i] <= K) 
                answer++;
        }
        
        return answer;
    }
}