[Algorithm] 프로그래머스 합승택시-경유지포함 | C++

※ [18회] E-PPER(기출) : 합승택시요금

[18회] E-PPER(기출) : 합승택시요금 - 구름LEVEL (goorm.io)

구름LEVEL

---

2022.09.09 - [c++/최단경로] - [Algorithm] 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 백준 11404

[Algorithm] 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 백준 11404

문제 해결 TIP

• 플로이드-워셜 알고리즘으로 최소비용 경로를 파악한 후, 경유지 조건을 체크한다.
• 이 문제는 s에서 출발해서 i까지 합승 후, 따로 따로 i부터 a까지, i부터 b까지 가는 최소 비용을 구하는 문제이다. 이때 반드시 경유지 c까지는 합승해야 한다는 조건이 있다.
• 따라서 최소비용(s->c) + 최소비용(c->i) + 최소비용(i->a) + 최소비용(i->b) 를 구하는 문제이다. (단, c==i가 될 수 있다.)

문제 해결 풀이

1. nxn 크기의 그래프에서 '최소 비용'을 구하기 위해 dp를 활용한다. 모든 노드에서 모든 노드까지의 최단 경로(최소 비용)를 구하는 플로이드-워셜로 접근한다. (일단 nxn 배열의 모든 원소를 INF로 채워 넣는다. -> 나중에 알고리즘 과정에서 최솟값으로 갱신된다.)
2. 주어진 입력값으로 초기화를 한다. 자기 자신과의 비용은 0 (i==j 일때)이다. 이 문제에선, a->b, b->a 의 비용이 같은 양방향 그래프이다.
3. 플로이드-워셜을 적용하여 모든 노드끼리의 "쌍"별로 최단경로가 저장된 2차원 배열을 구한다. (i에서 j로 갈 때, i->j와 i->k->j 중 더 짧은 경로로 갱신) graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j])
4. 경유지를 고려하여 최소 비용을 계산한다. (출발지: s, 경유지: c, 목적지1: a, 목적지2: b) 모든 i=1,2,3...n 중에서 (플로이드-워셜을 적용한) graph[s][c] + graph[c][i] + graph[i][a] +graph[i][b] 의 결과가 최솟값 일 때 최소 비용이 된다.

---

#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e7 * 2; //최대 n-1개의 간선을 지나게 됨
int graph[201][201]={0,};

int solution(int n, int s, int a, int b, vector<vector<int>> fares, int lay) {
    int answer = INF;

    // 1. nxn 배열의 모든 원소를 INF로 채워 넣는다. (자기 자신은 0으로)
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            graph[i][j]=INF;
        }
        graph[i][i]=0; //자기 자신과의 비용은 0
    }
    
    // 2. 주어진 입력값으로 초기화를 합니다.
    for(int i=0;i<fares.size();i++){
        graph[fares[i][0]][fares[i][1]]=fares[i][2];
        graph[fares[i][1]][fares[i][0]]=fares[i][2];
    }
    
    // 3. 플로이드-워셜을 적용
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j]); //k 지점을 지나는 것이 더 저렴할 경우 업데이트
            }
        }
    }
    
    // 4. 최소 비용 계산
    // lay는 경유지
    for(int i=1;i<=n;i++){
        answer=min(answer,graph[s][lay]+graph[lay][i]+graph[i][a]+graph[i][b]);
    }
    
    return answer;
}

int main() {
	int n, s, a, b, c, u, v, w;
	cin >> n >> s >> a >> b >> c;

	// 테스트 케이스 개수 : 9
	int i = 9;
	vector<vector<int>> fares;
	while (i--) {
		cin >> u >> v >> w;
		fares.push_back({ u,v,w });
	}

	int ans = solution(n, s, a, b, fares, c);
	cout << ans;
}