[프로그래머스] 12978. 배달 (C++)

코딩테스트 연습 - 배달

문제 설명

1. 각 마을은 양방향으로 연결됨

2. 마을 N까지의 거리가 K 이하면, 배달 가능

3. 마을 1에서 배달을 갈 수 있는 마을의 개수 출력

 

풀이

플로이드 와샬 알고리즘

1. 각 마을간의 거리를 입력받을 때마다 배열에 저장 (양방향으로!!)

1-1. 마을 a와 b 사이의 경로가 2개 이상일 수 있으니, 입력받을 때마다 최솟값으로 갱신

2. 마을 기준으로 반복문 돌면서 최소 거리 갱신

3. 마을 a -> a 비용은 0

4. 마을 1 (배열의 첫번째 행) 과 다른 마을들 사이의 거리 중, K 이하인 거리가 존재하면 answer++

 

코드

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;

int graph[51][51];
int INF = 10001;

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    memset(graph, INF, sizeof(graph));
    for(int i=0; i<road.size(); i++) {
        graph[road[i][0]][road[i][1]] = graph[road[i][1]][road[i][0]] = min(graph[road[i][0]][road[i][1]], road[i][2]);
    }
    for(int k=1; k<=N; k++) {
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
            }
        }
    }
    for(int i=1; i<=N; i++) graph[i][i] = 0;
    for(int i=1; i<=N; i++) {
        if(graph[1][i] <= K) answer++;
    }
    return answer;
}