[프로그래머스/Level2] 배달 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• 플로이드 와샬

N 크기가 크지 않아서 플로이드 와샬을 사용했다.

i번 마을에서 j번 마을까지 이동 가능한지 확인하기 위해, 1부터 N까지 중간 지점 k의 (i,k)를 연결하는 경로가 존재하고, (k,j)를 연결하는 경로가 존재한다면 i에서 j번 마을로 배달 가능하다.

dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j])

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static final int INF = Integer.MAX_VALUE;
    
    public int solution(int N, int[][] road, int K) {        
        int[][] dp = new int[N+1][N+1];
        
        // dp 초기화
        for(int i = 0 ; i <= N ; i++)
           Arrays.fill(dp[i], INF);
        
        for(int i = 1 ; i <= N ; i++)
            dp[i][i] = 0;
        
        // 입력값 중 더 작은 값으로 갱신
        for(int[] r : road) {
            dp[r[0]][r[1]] = Math.min(dp[r[0]][r[1]], r[2]);
            dp[r[1]][r[0]] = Math.min(dp[r[0]][r[1]], r[2]);;
        }
        
        for(int k = 1 ; k <= N ; k++) { // 중간 지점
            for(int i = 1 ; i <= N ; i++) { // 출발지
                for(int j = 1 ; j <= N ; j++) { // 도착지
                    if(i == j || j == k || k == i)  continue;
                    
                    if(dp[i][k] != INF && dp[k][j] != INF) {    // (i,k)와 (k,j)를 연결 가능한 경우
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
                    }
                }
            }            
        }
                
        int answer = 0;
        for(int i = 1 ; i <= N ; i++) {
            if(dp[1][i] <= K)
                answer++;
        }
 
        return answer;
    }
}

 

 

 

 

 

➕ 다른 풀이 방식

다익스트라를 활용한 풀이

[프로그래머스] 배달(Java, 자바)

 

 

BFS를 활용한 풀이

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

---

27분 소요,,

 

 

 

1회독	2회독	3회독	4회독	5회독
V