합승택시요금 문제보기
다익스트라, 플로이드 와샬 알고리즘 보기
1. 문제 정의
노드와 무향 간선이 포함된 그래프가 주어졌을 때, 동일한 출발점에서 시작하여 서로 다른 도착점으로 이동하는데 소비하는 최소 비용을 구하는 문제 입니다. 문제에서 주어지는 포인트는 "출발점 s / 도착점 a / 도착점 b" 총 3가지 입니다. 2명이 동일한 출발점 s에서 시작해 임의의 i 지점까지 같이 이동하고, 이후 쪼개져서 각자 도착점 a와 도착점 b로 도착하는 모든 경로 합의 최소 값을 구해야 합니다.
2. 풀이 방법 탐색
s: 출발점
i: 임의의 지점(같이 택시를 탑승하는 종점)
a: a가 도착점
b: b의 도착점
s, i, a, b가 위와 같다고 했을 때, 이 문제에서 구해야하는 경로는 3가지 입니다.
1) s -> i
2) i -> a
3) i -> b
이 문제에서는 택시 요금의 합이 최소가 나올 i 지점이 무엇일지를 알아야 합니다. 왜냐하면 "s -> i"인 같은 택시를 타고 이동한 택시요금을 "한 번만" 지불해야 하기 때문입니다.
(1) 다익스트라로 풀이
주어지는 그래프는 무향 그래프로 임의의 i, j 노드가 있을 때, i -> j 경로나 j -> i 경로나 같습니다. 그래서 구해야 하는 경로는 "s -> i, a -> i, b -> i" 로 풀이가 가능합니다. 이 때 노드 1부터 노드 n까지 범위 중에서 임의로 선택한 노드가 i이기 때문에, 출발점 각각 모든 다른 노드까지의 최단 경로가 필요합니다. 이러한 알고리즘과 일치하는 방법이 다익스트라가 있습니다.
다익스트라의 목적은,
임의의 노드 A부터
다른 노드들 까지의
최단 거리
(2) 플로이드 와샬로 풀이
이 문제는 플로이드 와샬로도 풀이가 가능합니다. 주어지는 테스트 케이스마다 최단 경로가 될 i가 무엇인지는 모르겠지만, 일단 모든 노드간의 최단 경로들을 구해놓고 1부터 n까지 i일 지점 하나를 선택해 최소합이 무엇인지 탐색하면 되기 때문입니다.
플로이드 와샬의 목적은,
모든 노드 사이의
최단 거리
3-1. 다익스트라 풀이
(1) 조건 체크(초기화 및 메모리 할당)
다익스트라에서 거리 값 정보를 담을 배열을 할당해 줘야 하는데, 우선 가장 큰 값으로 초기화가 필요합니다. 다익스트라 탐색으로 거리값을 갱신하면서, 이미 저장되어 있는 값보다 작은지를 비교하며 갱신해줘야 하기 때문입니다.
그리고 우선순위큐를 사용해 큐에 저장되어 있는 거리 정보가 작은 순으로 정렬되어 있어야 하기에, 크기 비교 operator 메소드를 오버라이딩하는 과정도 필요합니다.
#include <string>
#include <vector>
#include <queue>
using namespace std;
#define INF 2100000000 // 나름대로 큰 값 디파인
struct cmp {
bool operator()(const pair<int, int> &a, const pair<int, int> &b) {
return a.second > b.second;
}
};
priority_queue <pair<int, int>, vector<pair<int, int>>, cmp> q;
int cost[201][201];
int faresSize;
int dijk[3][201]; // dijk[0]: s시작점, dijk[1]: a시작점, dijk[2]: b시작점이 때 거리 값 정보를 담을 dijk 2차원 배열에서
0번째 row는 s시작점에 대한 정보
1번쨰 row는 a시작점에 대한 정보
2번째 row는 b시작점에 대한 정보
를 저장하도록 설정합니다.
(2) 그래프 만들기
다익스트라 탐색을 하기 위해서는 노드와 간선이 포함된 그래프가 필요합니다. 이 문제에서 입력으로 제공하는 파라미터 중, vector<vector<int>> fares 를 이용해 그래프를 만들어 줍니다.
typedef struct {
int to, val;
}vtx;
vector <vtx> v[201];
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
int answer = INF;
faresSize = fares.size();
// 그래프 생성
for (int i = 0; i < faresSize; i++) {
int node1 = fares[i][0];
int node2 = fares[i][1];
int fee = fares[i][2];
v[node1].push_back({ node2, fee });
v[node2].push_back({ node1, fee });
cost[node1][node2] = cost[node2][node1] = fee;
}
return answer;
}파라미터로 주어지는 fares에는 두 노드 사이의 간선 정보가 1개만 등장하지만, 무향 그래프 이므로 node1 -> node2와 node2 -> node1 모두 같은 간선을 갖도록 해줍니다.
(3) 다익스트라 구현하기
// start -> end 최단 경로 구하기
int dijkstra(int n, int start, int end) {
for (int i = 1; i <= n; i++) {
dijk[i] = INF; // 큰 값으로 초기화
}
dijk[start] = 0;
q.push(start);
while (!q.empty()) {
int idx = q.top();
q.pop();
for (int i = 0; i < v[idx].size(); i++) {
int next = v[idx][i].to;
int val = v[idx][i].val;
if (dijk[next] > dijk[idx] + val) {
dijk[next] = dijk[idx] + val;
q.push(next);
}
}
}
return dijk[end];
}
(4) 결과 값 갱신
다익스트라 알고리즘에서는 출발점이 정해만 진다면, 다른 모든 노드들까지의 최단 경로를 탐색하게 되므로 최종 아웃풋인 최단 경로 합을 저장하는 배열 값이 전부 다릅니다. 다시 말해 s지점에서 출발한 다익스트라 경로합, a지점에서 출발한 다익스트라 경로합, b지점에서 출발한 다익스트라 경로합 각각의 결과가 전부 다릅니다. 따라서 각각 3번의 다익스트라를 통해 문제를 해결해야 합니다. 그리고 완성된 다익스트라 결과 거리값 배열을 활용해, 문제에서 요구하는 결과 값을 탐색합니다.
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
for (int i = 1; i <= n; i++) {
// (s -> i 최단거리) + (i -> a 최단거리) + (i -> b 최단거리)
int res = dijkstra(n, s, i) + dijkstra(n, i, a) + dijkstra(n, i, b);
if (answer > res) answer = res;
}
return answer;
}
(5) 최종 소스
#include <string>
#include <vector>
#include <queue>
using namespace std;
#define INF 2100000000
typedef struct {
int to, val;
}vtx;
priority_queue <int> q;
vector <vtx> v[201];
int cost[201][201];
int faresSize;
int dijk[201];
// start -> end 최단 경로 구하기
int dijkstra(int n, int start, int end) {
for (int i = 1; i <= n; i++) {
dijk[i] = INF;
}
dijk[start] = 0;
q.push(start);
while (!q.empty()) {
int idx = q.top();
q.pop();
for (int i = 0; i < v[idx].size(); i++) {
int next = v[idx][i].to;
int val = v[idx][i].val;
if (dijk[next] > dijk[idx] + val) {
dijk[next] = dijk[idx] + val;
q.push(next);
}
}
}
return dijk[end];
}
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
int answer = INF;
faresSize = fares.size();
// 트리 생성
for (int i = 0; i < faresSize; i++) {
int node1 = fares[i][0];
int node2 = fares[i][1];
int fee = fares[i][2];
v[node1].push_back({ node2, fee });
v[node2].push_back({ node1, fee });
cost[node1][node2] = cost[node2][node1] = fee;
}
for (int i = 1; i <= n; i++) {
// (s -> i 최단거리) + (i -> a 최단거리) + (i -> b 최단거리)
int res = dijkstra(n, s, i) + dijkstra(n, i, a) + dijkstra(n, i, b);
if (answer > res) answer = res;
}
return answer;
}
3-2. 플로이드 와샬 풀이
(1) 조건 체크(초기화 및 메모리 할당)
플로이드 와샬은 임의의 노드 i, j 간의 최소 비용 정보를 저장할 2차원 배열이 필요합니다. 여기서는 다익스트라와 다르게 우선순위 큐가 필요가 없습니다.
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 1000000000
int FloydWarshallCost[201][201];
(2) 플로이드 와샬 배열 초기화
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
int answer = INF;
int faresSize = fares.size();
memset(FloydWarshallCost, -1, sizeof(FloydWarshallCost));
// 주어진 간선 초기화
for (int i = 0; i < faresSize; i++) {
int node1 = fares[i][0];
int node2 = fares[i][1];
int cost = fares[i][2];
FloydWarshallCost[node1][node2] = FloydWarshallCost[node2][node1] = cost;
}
return answer;
}
(3) 다익스트라 구현하기
void FloydWarshall(int n, int s, int a, int b) {
// 노드간 거리 초기화
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) FloydWarshallCost[i][j] = 0;
else {
if (FloydWarshallCost[i][j] == -1) FloydWarshallCost[i][j] = INF;
}
}
}
// 플로이드 와샬 알고리즘
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
FloydWarshallCost[i][j] = min(FloydWarshallCost[i][j], FloydWarshallCost[i][k] + FloydWarshallCost[k][j]);
}
}
}
}플로이드 와샬 알고리즘을 이용해 i = 1, j = 1부터 i = n, j = n 까지, 중간에 k 지점을 거쳐보며 최소 값을 갱신하도록 3중 for문으로 구현해 줍니다.
(4) 결과 값 갱신
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
...
for (int i = 1; i <= n; i++) {
// (s -> i) + (i -> a) + (i -> b) 최소합 갱신
int sum = FloydWarshallCost[s][i] + FloydWarshallCost[i][a] + FloydWarshallCost[i][b];
if (sum < answer) answer = sum;
}
return answer;
}완성된 플로이드 와샬 최단거리 배열 정보를 이용해 문제에서 요구하는 결과 값을 갱신합니다. 이 때, i는 택시를 합승하여 움직이게된 최종 목적지 입니다.
(5) 최종 소스
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 1000000000
typedef struct {
int next, val;
}vtx;
vector <vtx> v[201];
int FloydWarshallCost[201][201];
void FloydWarshall(int n, int s, int a, int b) {
// 노드간 거리 초기화
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) FloydWarshallCost[i][j] = 0;
else {
if (FloydWarshallCost[i][j] == -1) FloydWarshallCost[i][j] = INF;
}
}
}
// 플로이드 와샬 알고리즘
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
FloydWarshallCost[i][j] = min(FloydWarshallCost[i][j], FloydWarshallCost[i][k] + FloydWarshallCost[k][j]);
}
}
}
}
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
int answer = INF;
int faresSize = fares.size();
memset(FloydWarshallCost, -1, sizeof(FloydWarshallCost));
// 주어진 간선 초기화
for (int i = 0; i < faresSize; i++) {
int node1 = fares[i][0];
int node2 = fares[i][1];
int cost = fares[i][2];
FloydWarshallCost[node1][node2] = FloydWarshallCost[node2][node1] = cost;
}
FloydWarshall(n, s, a, b);
for (int i = 1; i <= n; i++) {
// (s -> i) + (i -> a) + (i -> b) 최소합 갱신
int sum = FloydWarshallCost[s][i] + FloydWarshallCost[i][a] + FloydWarshallCost[i][b];
if (sum < answer) answer = sum;
}
return answer;
}