[프로그래머스 *Java] - 배달

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

프로그래머스

 

조건

제한 시간 : 1시간

 

간만에 그래프 문제를 풀어서 그런지, 그냥 공부하듯이 문제를 푼 거 같다.
이 문제는 그래프 문제에서 다익스트라, 플로이드 와샬 알고리즘을 이용해서 풀수 있었다.
플로이드 와샬 알고리즘을 접해본 적이 없어, 관련 알고리즘을 찾아보며 공부한 뒤
문제에 적용해서 문제를 풀었다.

알고리즘 기법 Flow
1. 초기 세팅 해주기. (0, INF)
2. Input 값(양방향)으로 2차 초기세팅 해주기
3. 알고리즘 적용하기
4. 값 도출

 

 

import java.util.*;

class Solution {
    final int INF = 500_001;
    
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        int[][] floyd = new int[N][N];

        for (int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(i == j) 
                    floyd[i][j] = 0;
                else 
                    floyd[i][j] = INF;
            }
        }
        
        for (int i = 0; i < road.length; i++) {
            // 원래 있는 길이 더 적으면 pass
            if(floyd[road[i][0] - 1][road[i][1] - 1] < road[i][2]) continue;
            
            // 양방향 연결
            floyd[road[i][0] - 1][road[i][1] - 1] = road[i][2];
            floyd[road[i][1] - 1][road[i][0] - 1] = road[i][2];
        }   
        
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                if (i == k) continue;
                for (int j = 0; j < N; j++) {
                    if (i == j || j == k) continue; 
                    floyd[i][j] = Math.min(floyd[i][j], floyd[i][k] + floyd[k][j]);
                }
            }
        }
        
        //for (int[] row : floyd) System.out.println(Arrays.toString(row));
        for (int i = 0; i < floyd[0].length; i++) {
            if(floyd[0][i] <= K) {
                answer++;
            }
        }
        
        return answer;
    }
}

 

 

플로이드-와샬 알고리즘이 생소하다면? 아래에 내가 블로그 정리해둔 글을 읽으면 좋을 거 같습니다.

https://devnuts.tistory.com/133

[알고리즘] - 플로이드-와샬 알고리즘