[프로그래머스_카카오] 합승 택시 요금
- 양방향 가중치 그래프다
문제 이해하기
- 끝까지 둘이서 같은 택시를 타야한다고 생각했는데 그런 문제는 아니다.
- "출발"~ "특정지점" 까지 같이 움직인 후 ,
- "특정지점" ~ "각자의 목표" 까지는 각자 움직인다 . (당연하다, 계속 같이 타고 다니는게 더 손해다)
- 물론, 합승을 아예 하지 않는 것이 더 최소인 경우도 존재한다.
- 최소 경로 알고리즘을 떠올린다면
- 디익스트라 : 하나의 노드에서 각 노드 까지의 최소 경로 ( 도달할 수 없는 경우 INF 값을 갖는다)
- 하나의 Table에 하나의 노드에서 각 노드까지의 거리가 저장되어있다.
- 매 단계에서는, 최소 경로를 가진 노드를 뽑아 , 해당 노드를 거쳐 인접 노드까지 가는 거리를 계산한다.
- 그러면 뽑혔던 노드는, 그 노드까지의 최소 거리는 어차피 확정 된 것이고
- 뽑혔던 노드의 인접 노드들까지의 계산된 거리가, 이제까지 거리보다 최소 비용이라면 update를 진행 해 준다.
- 플로이드 워샬 : 모든 노드에서 다른 노드까지의 최단 경로를 모두 계산한다. → 2D TABLE에 값을 갱신해 나간다. DP 유형에 속한다.
- 디익스트라 : 하나의 노드에서 각 노드 까지의 최소 경로 ( 도달할 수 없는 경우 INF 값을 갖는다)
- 문제에서 s,a,b는 1이상 n이하의 자연수이며, 각기 서로 다른 값이라고 한다.
문제 풀이
-
같이 갈 최소의 경유지점을 찾는다고 생각해서는 안 될 것 같다
-
오히려 약간의 전체탐색이 필요할 것 같다. 왜냐하면. 합승을 할 수도 안 할수도 있고. 한다고 하더라도 어디까지 합승하는가에 따라 결과가 다를 것이기 때문이다.
-
플로이드 워샬 은 O(n^3)인데 플로이드 워샬을 통하여,각 노드에서 다른 노드까지의 모든 경로의 최소 값을 찾게 된다. (n이 현재 200이기 때문에 괜찮아 보인다)
- Das + Dbs
-
특정한 경유지점 c가 있다 하자
1. Dsc + Dac + Dbc결국 답은 Min (1 , 2) 라고 생각이 들었다.
-
여기서 모든 2번 경우들의 최소값을 찾는다고 하더라도, 경유지점 c는 200개 밖에 없기 때문에 탐색이 가능한 듯 하다.
-
? 생각보다 괜찮을 지도..
-
한 번 플로이드 워샬 알고리즘을 사용해 보려 한다. 사용해 본지 너무 오래돼서 기억이 안 난다.
import java.util.*;
class Solution {
public final int INF = 500000000; //10만 x 10000은 해야지 10억이나옴
public int[][] dtable = new int[201][201];
public int gn;
// dtable 초기화
public void setting(int[][] fares) {
// 자기 자신까지는 0
for (int r = 0; r <= gn; r++) {
Arrays.fill(dtable[r], INF);
dtable[r][r] = 0;
}
int v1 = 0, v2 = 0, c = 0;
// 간선정보 세팅
for (int r = 0; r < fares.length; r++) {
// fares[r]은 3개의 원소로 이루어짐. -> 이를 양방향으로 dtable에 update
v1 = fares[r][0];
v2 = fares[r][1];
c = fares[r][2];
dtable[v1][v2] = c;
dtable[v2][v1] = c;
}
}
public void floyd() {
// c를 거치는 경우가 더 최소인 경우 업데이트한다.
for (int c = 1; c <= gn; c++) {
for (int v1 = 1; v1 <= gn; v1++) {
for (int v2 = 1; v2 <= gn; v2++) {
// dtable[v1][v2] dtable[c][v1]+dtable[c][v2]
if (dtable[v1][v2] > (dtable[c][v1] + dtable[c][v2])) {
dtable[v1][v2] = dtable[c][v1] + dtable[c][v2];
dtable[v2][v1] = dtable[c][v1] + dtable[c][v2];
}
}
}
}
}
// n은 노드의 개수, s는 시작점, a는 목표 1, b는 목표 2. fares는 간선정보
public int solution(int n, int s, int a, int b, int[][] fares) {
int answer = 0;
gn = n;
setting(fares);
floyd();
// 세팅된 dtable을 이용하기
// 먼저 Das + Dbs
int simpCost = dtable[a][s] + dtable[s][b];
// Dsc + Dca +Dcb
// s를 제외한 점들을 경유지라고 해보자. 아니다 s도 포함시키면 simpCost도 포함되네
int min = Integer.MAX_VALUE;
int cur = 0;
for (int c = 1; c <= n; c++) {
cur = dtable[s][c] + dtable[c][a] + dtable[c][b];
min = Math.min(min, cur);
}
answer = Math.min(min, simpCost);
return answer;
}
}정확성 테스트
테스트 1 〉 통과 (0.07ms, 69.6MB)
테스트 2 〉 통과 (0.07ms, 69.7MB)
테스트 3 〉 통과 (0.06ms, 67.8MB)
테스트 4 〉 통과 (0.10ms, 58.9MB)
테스트 5 〉 통과 (0.13ms, 66.9MB)
테스트 6 〉 통과 (0.16ms, 68.5MB)
테스트 7 〉 통과 (0.12ms, 70.8MB)
테스트 8 〉 통과 (0.20ms, 60.1MB)
테스트 9 〉 통과 (0.27ms, 68.1MB)
테스트 10 〉 통과 (0.34ms, 62MB)
효율성 테스트
테스트 1 〉 통과 (9.36ms, 52.5MB)
테스트 2 〉 통과 (39.23ms, 57.1MB)
테스트 3 〉 통과 (30.46ms, 53.6MB)
테스트 4 〉 통과 (34.72ms, 52.4MB)
테스트 5 〉 통과 (40.98ms, 54.6MB)
테스트 6 〉 통과 (27.24ms, 53MB)
테스트 7 〉 통과 (41.96ms, 64.2MB)
테스트 8 〉 통과 (45.15ms, 63.6MB)
테스트 9 〉 통과 (23.31ms, 65.4MB)
테스트 10 〉 통과 (48.20ms, 64MB)
테스트 11 〉 통과 (53.14ms, 64.4MB)
테스트 12 〉 통과 (86.96ms, 62.6MB)
테스트 13 〉 통과 (32.05ms, 59.2MB)
테스트 14 〉 통과 (105.22ms, 62.6MB)
테스트 15 〉 통과 (39.18ms, 60MB)
테스트 16 〉 통과 (30.62ms, 52.8MB)
테스트 17 〉 통과 (23.98ms, 52.7MB)
테스트 18 〉 통과 (25.59ms, 54.4MB)
테스트 19 〉 통과 (26.11ms, 53.6MB)
테스트 20 〉 통과 (34.43ms, 57.2MB)
테스트 21 〉 통과 (26.10ms, 55MB)
테스트 22 〉 통과 (52.60ms, 59.7MB)
테스트 23 〉 통과 (39.99ms, 59.9MB)
테스트 24 〉 통과 (40.83ms, 60MB)
테스트 25 〉 통과 (28.55ms, 53MB)
테스트 26 〉 통과 (30.77ms, 52.9MB)
테스트 27 〉 통과 (41.38ms, 57.1MB)
테스트 28 〉 통과 (35.04ms, 52.9MB)
테스트 29 〉 통과 (12.23ms, 53.5MB)
테스트 30 〉 통과 (9.42ms, 52.3MB)
다른 사람 풀이를 보니 다익스트라도 사용
- 다익스트라를 n 번 수행 하는 거로 생각할 수도 있다.
- 다익스트라는 O(VlogE)의 효율을 갖기 때문에 , 여기서는 dtable 세팅하는데에 O(V^2logE)의 효율을 가질 수 있다. 앞선 O(V^3) 보다 좋은 효율을 갖는다.
