프로그래머스 (C/C++, Java) 72413 : 합승 택시 요금

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

프로그래머스

 

---

풀이

헤어지는 지점을 어떻게 잡아야 할 지 모르겠어서 다른 분들의 접근방식을 참고했다.

모든 분기에서 헤어진다는 가정 하에 path[s][node] + path[node][a] + path[node][b]의 최솟값을 구하면 된다.

s, a, b 지점은 고정되어 있지만 헤어지는 node가 다 다르므로 플로이드-와샬 알고리즘을 이용하여 모든 노드 간의 최소 거리를 구했다.

이후 모든 분기점을 node 지점으로 지정하며 최소값을 구했다.

---

C/C++ 코드

#include <string>
#include <vector>
#include <climits>

using namespace std;
#define INF INT_MAX
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = INF; 
    
    // 지도 초기화
    int path[201][201] = {0, };
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < n + 1; j++) {
            if (i == j) continue;
            path[i][j] = INF;
        }
    }

    for (int i = 0; i < fares.size(); i++) {
        int start = fares[i][0];
        int end = fares[i][1];
        int weight = fares[i][2];

        path[start][end] = path[end][start] = weight;
    }

    // 모든 노선 간의 거리 확인
    for (int k = 1; k < n + 1; k++) {
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (path[i][k] != INF && path[k][j] != INF)
                    path[i][j] = min(path[i][j], path[i][k] + path[k][j]);
            }
        }
    }

    // 헤어지는 노드를 바꿔가며 최소값 찾기
    for (int i = 1; i < n + 1; i++) {
        if (path[s][i] != INF && path[i][a] != INF && path[i][b] != INF)
            answer = min(answer, path[s][i] + path[i][a] + path[i][b]);
    }
    return answer;
}

 

Java 코드

import java.util.*;

class Solution {
    private int[][] path;
    private static final int INF = Integer.MAX_VALUE;
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = INF;
        
        // 지도 초기화
        path = new int[n + 1][n + 1];
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (i == j) continue;
                path[i][j] = INF;
            }
        }

        for (int i = 0; i < fares.length; i++) {
            int start = fares[i][0];
            int end = fares[i][1];
            int weight = fares[i][2];
            
            path[start][end] = path[end][start] = weight;
        }
        
        // 모든 노선 간의 거리 확인
        for (int k = 1; k < n + 1; k++) {
            for (int i = 1; i < n + 1; i++) {
                for (int j = 1; j < n + 1; j++) {
                    if (path[i][k] != INF && path[k][j] != INF)
                        path[i][j] = Math.min(path[i][j], path[i][k] + path[k][j]);
                }
            }
        }
        
        // 헤어지는 노드를 바꿔가며 최소값 찾기
        for (int i = 1; i < n + 1; i++) {
            if (path[s][i] != INF && path[i][a] != INF && path[i][b] != INF)
                answer = Math.min(answer, path[s][i] + path[i][a] + path[i][b]);
        }
        return answer;
    }
    
}