문제 URL : programmers.co.kr/learn/courses/30/lessons/72413
코딩테스트 연습 - 합승 택시 요금
6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4
programmers.co.kr
문제 접근법 :
floyd 알고리즘으로 해결했습니다.
floyd 알고리즘은 모든 노드에서 모든 최단거리를 n^3만에 알수있고
단순히 s에서 출발해서 A와 B가 x라는 지점까지 함께 가고 x지점에서 a지점으로 그리고 x지점에서 b지점을 가야하는 문제입니다.
그림으로 보자면
도스창은 floyd 알고리즘으로 1~6까지 구한 최단거리들이고
그것을 계산해낸것을 보여주었습니다.
4->1을가고 1->2와 1->6으로 나뉘어져 갔을때는 98 이렇게만 보면 아직 잘모를수있습니다.
그렇다면 4->3을가고 3->2와 3->6을갔을때 99입니다. 음 조금더 비용이 늘었습니다. 여기서 잘생각 해보세여
4->3을 갔다는것은 어떤것을 의미하는걸까요??
A와 B가 1지점을 거치고 3을 함께가고 3에서 흩어졌다는것을 의미합니다.
그리고 4->5를가고 5->2, 5->6은 A와 B가 1지점을 거치고 5에서 흩어졌다는것을 의미한다는것
왜 그런의미가 될까요? 여기서 플로이드 알고리즘을 잘 공부하셨다면 바로 이해하실겁니다.
플로이드 알고리즘 이용하여 모든 간선의 비용을 구한 W[i][j]라는 뜻은 w[i][k] - > w[k][j]의 의미를 내포하고있습니다.
쉽게 풀이하자면 k는 어떤 지점들을 거쳐서 j를 향해 최단거리를 구했기때문에
4->5 - >2,6은
4-(1)-5-2
4-(1)-5-6 즉 어느지점을 거쳤다는것을 내포했다는 의미를 알면 풀수있는 문제입니다.
즉 출발지점 s -> x -> a+b 지점을 구해 가장 최소의 답을 구하면 되겠지요
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
//By 콩순이냉장고
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
int w[201][201];
void floyd(int n) {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (w[i][k] + w[k][j] < w[i][j]) {
w[i][j] = w[i][k] + w[k][j];
}
}
}
}
}
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
int answer = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
w[i][j] = 1e+8;
}
w[i][i] = 0;
}
for (int i = 0; i < fares.size(); i++) {
int v1 = fares[i][0];
int v2 = fares[i][1];
int c = fares[i][2];
w[v1][v2] = c;
w[v2][v1] = c;
}
floyd(n);
answer = w[s][a] + w[s][b];
for (int i = 1; i <= n; i++) {
answer = min(answer, w[s][i] + w[i][a] + w[i][b]);
}
return answer;
}
|
cs |
제가 작년에 kakao 블라인드 코테를 봤었을땐 이문제를 그 당시에는 해결을 못했었습니다. 다익스트라로 해결하려고 노력했고 플로이드도 생각을했었지만 플로이드를 자세하게 생각하질 못했었네요
문제를 오늘 다시 처음부터 보고 다익스트라와 플로이드를 전부 써가면서 어떻게 생각을 조금 바꿔서 했더니 쉽게 풀려서 생각보다 당황했네요 ㅠ.ㅠ 그땐 못풀고 지금은 풀었다는게 안타깝지만 지금으 풀었으니 뿌듯한느낌?? 이래서 알고리즘을 공부할맛 나네여 ㅋㅋㅋ
궁금한점 혹은 모르는점 혹은 어떤질문이든 댓글은 환영입니다.
'프로그래머스' 카테고리의 다른 글
| 프로그래머스 괄호 회전하기 (0) | 2021.06.24 |
|---|---|
| 프로그래머스 2018 KAKAO BLIND RECRUITMENT[3차] n진수 게임 (0) | 2021.03.19 |
| 프로그래머스 야근지수 (0) | 2020.09.09 |
| 프로그래머스 섬 연결하기 (0) | 2020.09.09 |
| 프로그래머스 [3차] 자동완성(2018 KAKAO BLIND RECRUITMENT) (0) | 2020.09.09 |
