프로그래머스 - 배달 ( 플로이드-워셜 알고리즘 )

출처 : programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

 

고려사항

• 최단 경로 찾기 문제 중 플로이드-워셜 알고리즘을 사용했다.
• 일반적으로 플로이드 워셜 알고리즘은 모든 노드에서 모든 노드로의 최단거리를 한 번에 구할 수 있지만,
  시간복잡도가 n^3 으로 매우 느려서 노드의 수가 작아야지만 사용 가능하다.
  이 문제는 N이 50이라 사용 가능하다.
• INF 는 문제조건에 따라 다르지만 이 문제에서는 10억을 사용하면 충분하다.
  (35 라인의 fw[i][k] + fw[k][j] 에서 정수 범위를 벗어날 수 있으니 주의한다! )
  
  
• 13 - 32 를 통해 인접 행렬을 초기화 해준다.
  여러 간선으로 연결되어 있다면 그 중 최소 값으로! 연결 안되어 있으면 INF으로!
• 정말정말 간단한 3중 포문으로 모든 노드에서 모든 노드로 가는 최단 길이를 구해준다.
• f[1][i] 를 검사하면서 K보다 작은 경로의 수를 세어준다.
• 같은 문제를 다익스트라 알고리즘을 사용해서 풀어 작성한 글도 있다!

 

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 1000000000
using namespace std;
 
int fw[51][51];
 
int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    int from, to, w;
    
    for(int i=1;i<=N;++i){
        for(int j=1;j<=N;++j){
            if(i == j){
                fw[i][j] = 0;
            }else{
                fw[i][j] = INF;
            }
        }
    }
    
    for(vector<int> v : road){
        from = v[0];
        to = v[1];
        w = v[2];
        
        fw[from][to] = min(fw[from][to], w);
        fw[to][from] = min(fw[to][from], w);
    }
    
    for(int k=1;k<=N;++k){
        for(int i=1;i<=N;++i){
            for(int j=1;j<=N;++j){
                fw[i][j] = min(fw[i][j], fw[i][k] + fw[k][j]);
            }
        }
    }
    
    for(int i=1;i<=N;++i){
        if(fw[1][i] <= K){
            ++answer;
        }
    }
 
    return answer;
}