문제
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다. "무지"는 자신이 택시를 이용할 때 동료인 어피치 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을 알게 되었습니다. "무지"는 "어피치"와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 있을 지 계산해 보고 "어피치"에게 합승을 제안해 보려고 합니다.
위 예시 그림은 택시가 이동 가능한 반경에 있는 6개 지점 사이의 이동 가능한 택시노선과 예상요금을 보여주고 있습니다.
그림에서 A와 B 두 사람은 출발지점인 4번 지점에서 출발해서 택시를 타고 귀가하려고 합니다. A의 집은 6번 지점에 있으며 B의 집은 2번 지점에 있고 두 사람이 모두 귀가하는 데 소요되는 예상 최저 택시요금이 얼마인 지 계산하려고 합니다.
그림의 원은 지점을 나타내며 원 안의 숫자는 지점 번호를 나타냅니다.
지점이 n개일 때, 지점 번호는 1부터 n까지 사용됩니다.
지점 간에 택시가 이동할 수 있는 경로를 간선이라 하며, 간선에 표시된 숫자는 두 지점 사이의 예상 택시요금을 나타냅니다.
간선은 편의 상 직선으로 표시되어 있습니다.
위 그림 예시에서, 4번 지점에서 1번 지점으로(4→1) 가거나, 1번 지점에서 4번 지점으로(1→4) 갈 때 예상 택시요금은 10원으로 동일하며 이동 방향에 따라 달라지지 않습니다.
예상되는 최저 택시요금은 다음과 같이 계산됩니다.
4→1→5 : A, B가 합승하여 택시를 이용합니다. 예상 택시요금은 10 + 24 = 34원 입니다.
5→6 : A가 혼자 택시를 이용합니다. 예상 택시요금은 2원 입니다.
5→3→2 : B가 혼자 택시를 이용합니다. 예상 택시요금은 24 + 22 = 46원 입니다.
A, B 모두 귀가 완료까지 예상되는 최저 택시요금은 34 + 2 + 46 = 82원 입니다.
지점의 개수 n, 출발지점을 나타내는 s, A의 도착지점을 나타내는 a, B의 도착지점을 나타내는 b, 지점 사이의 예상 택시요금을 나타내는 fares가 매개변수로 주어집니다. 이때, A, B 두 사람이 s에서 출발해서 각각의 도착 지점까지 택시를 타고 간다고 가정할 때, 최저 예상 택시요금을 계산해서 return 하도록 solution 함수를 완성해 주세요.
만약, 아예 합승을 하지 않고 각자 이동하는 경우의 예상 택시요금이 더 낮다면, 합승을 하지 않아도 됩니다.
제한 사항
지점갯수 n은 3 이상 200 이하인 자연수입니다.
지점 s, a, b는 1 이상 n 이하인 자연수이며, 각기 서로 다른 값입니다.
즉, 출발지점, A의 도착지점, B의 도착지점은 서로 겹치지 않습니다.
fares는 2차원 정수 배열입니다.
fares 배열의 크기는 2 이상 n x (n-1) / 2 이하입니다.
예를들어, n = 6이라면 fares 배열의 크기는 2 이상 15 이하입니다. (6 x 5 / 2 = 15)
fares 배열의 각 행은 [c, d, f] 형태입니다.
c지점과 d지점 사이의 예상 택시요금이 f원이라는 뜻입니다.
지점 c, d는 1 이상 n 이하인 자연수이며, 각기 서로 다른 값입니다.
요금 f는 1 이상 100,000 이하인 자연수입니다.
fares 배열에 두 지점 간 예상 택시요금은 1개만 주어집니다. 즉, [c, d, f]가 있다면 [d, c, f]는 주어지지 않습니다.
출발지점 s에서 도착지점 a와 b로 가는 경로가 존재하는 경우만 입력으로 주어집니다.
입출력 예제
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
합승을 하지 않고, B는 3→2→1, A는 3→6→4 경로로 각자 택시를 타고 가는 것이 최저 예상 택시요금입니다.
따라서 최저 예상 택시요금은 (3 + 6) + (1 + 4) = 14원 입니다.
입출력 예 #3
A와 B가 4→6 구간을 합승하고 B가 6번 지점에서 내린 후, A가6→5` 구간을 혼자 타고 가는 것이 최저 예상 택시요금입니다.
따라서 최저 예상 택시요금은 7 + 11 = 18원 입니다.
첫 풀이 코드
import java.util.*;
class Solution {
public int solution(int n, int s, int a, int b, int[][] fares) {
int answer = Integer.MAX_VALUE;
// Start 지점 -> A 내리고 B 내리기
// 또는 B 내리고 A 내리기
// N은 200 (플로이드 워셜 가능)
// 이 때의 최저 요금을 구한다
// 비용 행렬 생성 (노드 시작 번호가 1부터)
int[][] cost = new int[n+1][n+1];
// 최댓값으로 초기화
for(int i = 1; i < n+1; i++) {
Arrays.fill(cost[i], Integer.MAX_VALUE);
cost[i][i] = 0; // 자기 자신은 0
}
// 비용 적어주기
for(int i = 1; i < fares.length+1; i++) {
cost[fares[i-1][0]][fares[i-1][1]] = fares[i-1][2];
cost[fares[i-1][1]][fares[i-1][0]] = fares[i-1][2];
}
// 플로이드 워셜
for(int i = 1; i < n+1; i++) {
for(int j = 1; j < n+1; j++) {
if(cost[j][i] == Integer.MAX_VALUE) continue;
for(int k = 1; k < n+1; k++) {
if(cost[i][k] == Integer.MAX_VALUE) continue;
cost[j][k] = Math.min(cost[j][i] + cost[i][k] , cost[j][k]);
}
}
}
for(int i = 1; i < n+1; i++) {
answer = Math.min(cost[s][i] + cost[i][a] + cost[i][b], answer);
}
return answer;
}
}결과 - 기본 테스트
결과 - 효율성 테스트
나의 풀이
처음에 다익스트라 문제로 생각하고 해결하고자 했다. 하지만, 노드의 크기가 500 이하이기 때문에(문제에서 3 이상 200 이하로 주어졌다) 플로이드 워셜을 통해 풀어도 시간초과가 나지 않고 로직이 더 간결할 것 같았다
플로이드-워셜
다익스트라가 출발 지점에서 다른 지점까지의 최단 경로를 찾는 알고리즘이라면, 플로이드-워셜은 모든 노드에서 모든 노드로 가는 최단거리를 찾는 알고리즘이다
또한 다익스트라 알고리즘은 음의 가중치일 때 사용 못하지만, 플로이드 워셜은 음의 가중치에서도 사용이 가능하다
하지만 플로이드-워셜의 시간 복잡도는 O(N3)에 수렴한다)
형태는 다음과 같다
// 비용 행렬 생성 (노드 시작 번호가 1부터)
int[][] cost = new int[n+1][n+1];
// 최댓값으로 초기화
for(int i = 1; i < n+1; i++) {
Arrays.fill(cost[i], Integer.MAX_VALUE);
cost[i][i] = 0; // 자기 자신은 0
}
// 비용 적어주기
for(int i = 1; i < fares.length+1; i++) {
cost[fares[i-1][0]][fares[i-1][1]] = fares[i-1][2];
cost[fares[i-1][1]][fares[i-1][0]] = fares[i-1][2];
}
// 플로이드 워셜
for(int i = 1; i < n+1; i++) {
for(int j = 1; j < n+1; j++) {
if(cost[j][i] == Integer.MAX_VALUE) continue;
for(int k = 1; k < n+1; k++) {
if(cost[i][k] == Integer.MAX_VALUE) continue;
cost[j][k] = Math.min(cost[j][i] + cost[i][k] , cost[j][k]);
}
}
}각 거리만큼의 행렬 생성
문제 풀이 코드에서 살펴보면, 처음 비용 행렬을 생성해준다. 이때 시작 지점을 0부터 하는가 1부터 하는가에 따라 +1을 해주거나 안 해주거나의 차이가 생긴다
여기서는 노드 시작 지점이 1부터이기 때문에 n+1만큼 해주었다
(n은 노드의 개수)
cost 행렬의 각 값을 최대 값으로 설정 + 자기 자신을 0으로 설정
문제에서 자기 자신이 자신으로 가는 비용은 항상 무료이기 때문에 0으로 설정해주고, 다른 경로로 가는 값은 MAX_VALUE로 설정해준다
주어진 fares 행렬의 2번 index인 비용을 cost에 넣어준다
fares는 시작 지점(0번 Index)과 연결 지점(1번 Index) 그리고 비용(2번 Index)로 구성되어 있다. 따라서cost[fares[i][0]][fares[i][1]] = fares[i][2]로 초기화해 줘야 한다
그런데 여기서 우리는 cost의 Index 0번을 사용하지 않기 때문에,
// 비용 적어주기
for(int i = 1; i < fares.length+1; i++) {
cost[fares[i-1][0]][fares[i-1][1]] = fares[i-1][2];
cost[fares[i-1][1]][fares[i-1][0]] = fares[i-1][2];
}다음과 같은 형태가 나오게 된다(fares의 i번 째 Index를 1씩 빼서 계산)
이후 핵심 로직인 플로이드-워셜 알고리즘을 사용한다
// 플로이드 워셜
for(int i = 1; i < n+1; i++) { // --- a
for(int j = 1; j < n+1; j++) { // --- b
if(cost[j][i] == Integer.MAX_VALUE) continue;
for(int k = 1; k < n+1; k++) { // --- c
if(cost[i][k] == Integer.MAX_VALUE) continue;
cost[j][k] = Math.min(cost[j][i] + cost[i][k] , cost[j][k]);
}
}
}플로이드 워셜은 3중 반복문으로 이루어져 있다.
각각에 주석으로 태깅을 했다
a : 가장 밖에 있는 반복문으로 중간 지점을 나타낸다
b : 중간에 있는 반복문으로 시작 지점을 나타낸다
c : 안쪽에 있는 반복문으로 도착 지점을 나타낸다
플로이드-워셜 알고리즘은 2가지 경우를 비교하여 cost 배열에 저장한다
j -> k로 가는 경우
1번 경우 : j에서 출발하여 k로 바로 가는 경우 ( cost[j][k] )
2번 경우 : j에서 출발하여 i를 거쳐서 k로 가는 경우 ( cost[j][i] + cost[i][k] )
이 두 경우를 비교하여 더 적은 비용을 cost[j][k]에 저장한다
그리고 만일 이동하려는 값 cost[j][i] 또는 cost[j][k] 가 초기에 지정한 값(나는 MAX_VALUE로 지정했다)이라면 연결이 되어있지 않은 상태이므로 continue로 무시하고 지나가주면 된다
문제에 맞는 답 구하기
각 지점에서 이동할 수 있는 최소 비용은 모두 구해놓았다
문제는 s에서 출발해서 a와 b로 가는 비용이 가장 적을 때의 cost값을 구해야 한다
그렇다면 플로이드-워셜을 통해 각 구간의 비용을 모두 계산하고 나서
cost [시작지점][중간지점] + cost[중간지점][A도착지점] + cost[중간지점][B도착지점] 이 가장 최소일 때의 값을 찾으면 된다!
마무리
만약 주어진 n(노드의 수)가 500 이상만 되어도 3중 반복문을 돌렸을 때 최악의 경우
500 * 500 * 500 = 125,000,000 가 나오게 된다. 1억 번 이상인 경우 1초가 넘기 때문에 시간 제한을 초과할 수 있다
따라서 노드 수를 확인한 뒤 진행해야 한다
만약 다익스트라 알고리즘을 두 번 사용한다면 시간 초과가 날 수 있지 않을까?
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| 짝지어 제거하기 (0) | 2023.11.29 |
|---|---|
| [프로그래머스] Lv.3 양과 늑대(Java) (0) | 2023.09.24 |
| [프로그래머스] Lv.2 전화번호 목록(java) (3) | 2023.08.24 |
