[프로그래머스] 72413 : 합승 택시 요금

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

프로그래머스

 

n이 500이하이므로 플로이드 워셜을 사용하던, 다익스트라를 사용하던 상관이 없다.

구현이 편리한 플로이드 워셜을 사용하였고, 효율성 풀이까지 통과하였다.

 

초기값 INF시 오버플로우 주의

거리의 초기값을 INF(매우 큰 수)를 둘 경우 초기값에 추가 값이 더해질때 오버플로우가 발생한다.(아주 작은 수(ex)-123456789)가 나온다.)

이 경우 min으로 거리 비교시 예상치 못한 값이 리턴될 수 있으므로 항상 거리가 INF 초기값일 경우 예외 처리하는 코드를 작성해주어야한다.

 

 

코드

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
int graph[204][204];
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    //1. 초기화 + 입력
    fill(&graph[0][0], &graph[0][0]+204*204, INF);
    for(int i=0;i<fares.size();i++){
        graph[fares[i][0]][fares[i][1]] = min(graph[fares[i][0]][fares[i][1]], fares[i][2]);
        graph[fares[i][1]][fares[i][0]] = min(graph[fares[i][1]][fares[i][0]], fares[i][2]);
    }
    for(int i=1;i<=n;i++){
        graph[i][i]=0;
    }
    //2. 플로이드-워셜 알고리즘 수행
    for(int k=1;k<=n;k++){
        for(int a=1;a<=n;a++){
            for(int b=1;b<=n;b++){
                graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b]);
            }
        }
    }
    //3. 합승할때의 최소 시간 구하기
    int answer = INF;
    for(int i=1;i<=n;i++){
        if (graph[s][i] == INF || graph[i][a]==INF||graph[i][b]==INF) continue;
        answer = min(answer, graph[s][i]+graph[i][a]+graph[i][b]);
    }
    if (graph[s][a]!=INF && graph[s][b]!=INF) answer = min(answer, graph[s][a]+graph[s][b]);

    return answer;
}

 

풀이

 

처음에는 어떻게 풀지 몰랐는데, 노드를 중심으로 거쳐가는 부분만 생각하면 쉽다!(level 3에서 제일 쉬운 편인듯!)