문제 푼 날짜 : 2021-06-30

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/72413

접근 및 풀이

Floyd-Warshall 또는 Dijkstra 알고리즘을 통해 풀어야하는 문제이다.
하지만, 문제를 푸는 내내 떠올리지 못했다...
무지성으로 DFS를 이용하여 코드만 짜려고해서 한창 헤매었다.
이 문제는 효율성 테스트까지 있기 때문에 이렇게 해서는 문제를 통과할 수가 없었다.

풀이를 찾아보던 중, 최단경로 문제는 Floyd-Warshall와 Dijkstra를 기본적으로 떠올릴 줄 알아야한다는 것을 알게 되었다.
알고리즘 수업때 배웠던 것들이지만 다시 한 번 공부하였고, Floyd-Warshall 알고리즘을 이용하여 문제를 풀 수 있었다.

문제 풀이는 https://youtu.be/NPZywlw28zc 이곳을 참조하였다.
대단하신 분인것 같다.

코드

#include <string>
#include <vector>

using namespace std;

#define INF 50000000

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = INF;
    int dist[201][201];
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                dist[i][j] = 0;
            } else {
                dist[i][j] = INF;
            }
        }
    }
    for (auto f : fares) {
        dist[f[0]][f[1]] = f[2];
        dist[f[1]][f[0]] = f[2];
    }
    
    // Floyd-Warshall
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    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;
}

피드백

더 열심히하자!