[Programmers] 2021 KAKAO BLIND RECRUITMENT : 합승 택시 요금 (C++) with 플로이드

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

프로그래머스

걸린 시간 : 31분 02초

---

프로그래머스에서 레벨2의 문제도 상당히 애를 먹은 게 많아 레벨3를 도전하기 어려웠다. 레벨3를 처음 도전해본 문제인데, 레벨2보다 쉬운데...? 싶은 느낌이다. 이거 레벨 누가 매기는 거지...

 

보고 문제를 해석하자마자 플로이드 알고리즘부터 생각났다. 하지만 플로이드 관련 문제를 푼지 오래된 것 같아 확실하게 공부해보고자 다른 문제를 풀고 넘어왔다. https://morenow.tistory.com/53 

[BOJ] 11404 : 플로이드 (C++)

그래서 실제로 이 문제만 생각하며 풀었을 땐 31분보다 더 걸렸을 것으로 생각되지만,,, 저 31분조차도 어이없는 실수때문에 허비된 것일 뿐 실제론 20분 안에 풀었다. (1시간 훨씬 넘게 걸린 레벨2 문제가 많았는데)

알고리즘

우선, 플로이드 알고리즘을 통해 임의의 정점 간 거리의 최솟값을 dist 배열에 저장해놓는다.

그 후 1 ~ n 까지의 모든 노드를 경유지로 생각해서 거리를 계산하면서 최솟값을 answer에 저장하면 끝난다.

주의할 점

오류를 겪어서 시간을 많이 허비한 부분이 역시나 off-by-one 오류였다. (누구나 많이 하는 "1 차이" 실수)

정점의 번호가 1 ~ n 임을 생각해서 0 ~ n-1 범위로 착각하지 않으려고 최선을 다했지만...

다음처럼 오류를 냈다.

for (int i = 1; i <= n; i++) 
    fill(dist[i], dist[i]+n, INF);

이러면 0부터 n-1까지 거리를 INF로 설정한다... 결국 다 출력해보고 나서야 깨달았다.

정답 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 30000000;
int dist[201][201];

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = INF;
    for (int i = 1; i <= n; i++) 
        fill(dist[i]+1, dist[i]+n+1, INF);
    for (int i = 1; i <= n; i++)
        dist[i][i] = 0;
    for (vector<int>& fare : fares) {
        dist[fare[0]][fare[1]] = fare[2];
        dist[fare[1]][fare[0]] = fare[2];
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        answer = min(answer, dist[s][i] + dist[i][a] + dist[i][b]);
    }
    return answer;
}