[2021 KAKAO BLIND RECRUITMENT] 합동 택시 요금

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

---

Floyd-Warshall 알고리즘 사용

문제 Point : 경유지를 무엇으로 설정할까? -> 결국 경유지를 다 탐색해봐야하는 완전 탐색 문제!

프로이드-와샬 알고리즘을 사용해서 해결할 수 있는 문제다. 이 문제의 핵심은 경유지를 무엇으로 정하는가 이다. 아래 그림에서 1,2,3,4,5,6 에 경유지를 둘 수 있다.

(여기서 경유지를 둔 다는 것은 출발점에서 경유지 지점까지 (S -> K)는 "무지"와 "프로도"가 함께 택시를 타고 경유지에서 각각의 도착지점까지 (K->A or K->B) 까지는 따로 택시를 탄다는 뜻이다.)

즉, (S->K) + (K->A) + (K->B) 중 최소값을 구하면 된다! 

주어진 그래프를 dist 이차원 배열로 먼저 바꿨다.

	1	2	3	4	5	6
1	0	INF	41	10	24	25
2	INF	0	22	66	INF	INF
3	41	22	0	INF	24	INF
4	10	66	INF	0	INF	50
5	24	INF	24	INF	0	2
6	25	INF	INF	50	2	0

이제 경유지를 거쳤을 때의 거리와 거치지 않았을 때의 거리 중 더 작은 값을 저장해주면 된다.

예를 들어 ,(4,6) 은 50인데 1 경유지를 거친다면 (4,1) -> (1,6) (10+25) 이다. 50 > 35이므로 4,6의 값을 35로 수정해준다.

 

이렇게 값을 최소화 시켜주면 문제는 다 끝났다.

주어진 출발점과, 프로도의 집, 무지의 집을 어떤 곳을 경유했을 때 가장 적은 비용인지 구해주면 된다.

    for(int k=1;k<=n;k++){
        answer=  min(answer,dist[s][k] + dist[k][a] + dist[k][b]);
    }
    

 

주의할 점!

보통 INF 변수를 int의 최대값 987654321 로 두는데 이렇게 둘 경우, 이 문제에서는 그렇게 두면 int의 범위를 벗어나는 경우가 생길 수도 있으므로 주의해야한다.

마지막에 dist[s][k] + dist[k][a] + dist[k][b] 에서 모두 INF 일 경우, int의 범위를 벗어난다.

그러므로 적당한 값으로 조정이 필요하다!

---

내 코드

#include <string>
#include <vector>

#define INF 40000000;
using namespace std;

int dist[201][201];

void floyd(int n){
    for(int k=1;k<=n;k++){ // k는 경유지
        for(int i=1;i<=n;i++){ //i : 시작점
            for(int j=1;j<=n;j++){ //j : 시작점
                if(dist[i][k] + dist[k][j] < dist[i][j]){ //dist[i][k] :i에서 k까지의 비용
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}


int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = INF;
    
    
    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 edge : fares){
        dist[edge[0]][edge[1]] = edge[2];
        dist[edge[1]][edge[0]] = edge[2];
    }
    floyd(n);
    
    
    for(int k=1;k<=n;k++){
        answer=  min(answer,dist[s][k] + dist[k][a] + dist[k][b]);
    }
    
    
    
    return answer;
}