[프로그래머스] 배달

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

코딩테스트 연습 - 배달

---

 

-풀이-

플로이드 와샬 알고리즘을 사용해서 문제를 풀것이다.

먼저 인접행렬을 만든다. maze[i][j]=k 는 i번 마을에서 j번 마을까지 가는 길중 걸리는 최소 시간이 k이다.

이 maze행렬을 모두 MAX값으로 초기화를 해준 뒤, road를 탐색하며, 각 마을간 거리를 업데이트 해준다. 단 a와 b마을 사이에 2개의 길이 있다면, 우리는 최단거리만 필요하므로, 작은 길로 업데이트를 해준다.

 

그런뒤, 플로이드 와샬 알고리즘을 이용하여 모든 마을에서 모든 마을까지의 최단거리를 구한 뒤, 1번 마을에서 2~N번 마을까지의 거리를 K와 비교하며, K이하가 된다면, answer++를 해준다.

 

-시간복잡도-

플로이드 와샬 알고리즘은 O(N³)이 된다.

 

-코드-

 

#include <iostream>
#include <vector>
#include<algorithm>
#define MAX 987654321
using namespace std;

int maze[51][51];

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 1;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            maze[i][j]=MAX;
        }
    }
    for(int i=0;i<road.size();i++){
        int a=road[i][0];
        int b=road[i][1];
        int c=road[i][2];
        if(maze[a][b]>=c){
            maze[a][b]=c;
            maze[b][a]=c;
        }
    }
    
    for(int k=1;k<=N;k++){
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                if(k==i||k==j||i==j) continue;
                maze[i][j]=min(maze[i][j],maze[i][k]+maze[k][j]);
            }
        }
    }
    for(int i=2;i<=N;i++){
        if(maze[1][i]<=K) answer++;
    }
    return answer;
}