-
프로그래머스 코딩테스트 연습 - 합승 택시 요금 (플로이드-와샬, 다익스트라) 본문
# 주소
https://school.programmers.co.kr/learn/courses/30/lessons/72413
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
# 문제
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다. "무지"는 자신이 택시를 이용할 때 동료인 어피치 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을 알게 되었습니다. "무지"는 "어피치"와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 있을 지 계산해 보고 "어피치"에게 합승을 제안해 보려고 합니다.
위 예시 그림은 택시가 이동 가능한 반경에 있는 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로 가는 경로가 존재하는 경우만 입력으로 주어집니다.
[입출력 예]nsabfaresresult
| 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,8], [4,3,9]] | 18 |
입출력 예 #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[][] arr = new int[n + 1][n + 1];
for(int i = 0; i <= n; i++){
Arrays.fill(arr[i], 20000001);
arr[i][i] = 0;
}
for(int i = 0; i < fares.length; i++){
int start = fares[i][0];
int end = fares[i][1];
int cost = fares[i][2];
arr[start][end] = arr[end][start] = cost;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int k = 1; k <= n; k++){
arr[j][k] = Math.min(arr[j][k], arr[j][i] + arr[i][k]);
}
}
}
int answer = Integer.MAX_VALUE;
for(int i = 1; i <= n; i++)
answer = Math.min(answer, arr[s][i] + arr[i][a] + arr[i][b]);
return answer;
}
}플로이드-와샬 기법으로 이 문제를 풀어보려고 합니다.
문제를 풀기 전 꼭 이해해야할 부분이 몇 가지 있는데 정리하고 넘어가겠습니다.
* 다익스트라와 플로이드-와샬 알고리즘의 차이점 *
다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로 가는 최단 거리를 구하는 알고리즘입니다. 따라서 다익스트라 알고리즘의 핵심은 최단거리는 최단거리와 그 합으로 표현될 수 있다는 것인데요. 이러한 이유로 현재까지 구한 최단거리를 계속해서 갱신해 나가는 방법으로 구현됩니다. 현재 최단거리 테이블에 저장된 값은 지금까지 방문한 모든 노드를 고려했을 때의 최단거리이므로 재방문할 필요가 없으며 음의 값은 사용할 수 없습니다.(여러 번 방문하면 그 값이 최단거리가 될 때 더 작아짐)
다익스트라 알고리즘을 쓰는 방법은 간단합니다.
1. 먼저 출발 노드를 설정합니다.
2. 현재 위치에서 갈 수 있는 모든 노드에 대한 최단거리를 업데이트 하는데 보통은 INF로 둡니다.
3. 현재 위치의 노드를 방문처리 하고 다음 방문할 노드는 방문하지 않은 노드 중 최단거리가 짧은 노드를 잡습니다.
4. 이후 해당 노드를 가는 경우에 대한 최소값을 모두 업데이트 하며 위 방법을 반복합니다.
이러한 탐색 법은 선형 탐색으로 이루어지며 시간 복잡도가 플로이드-와샬에 비해 크다는 경향을 가지고 있습니다.
이 문제를 개선하기 위해 우선 순위 힙을 이용할 수도 있습니다.
플로이드-와샬 기법을 알아보겠습니다.
플로이드-와샬은 간단히 얘기하자면 모든 정점에서 정점으로의 최단거리를 구하는 알고리즘입니다.
따라서 각 정점을 기준으로 최단 거리를 업데이트 해주는 방식이기 때문에 시간 복잡도가 낮습니다.
쓰는 방법은 더욱 간단합니다.
기본 상태에서 갈 수 있는 모든 노드의 값을 업데이트 합니다.
만약 1에서 출발한다면 1 -> 2에 대한 최단 거리를 업데이트 할 때 1 - > 3 - > 2가 빠른지, 1 - > 2로 바로 가는 것이 빠른지 비교해가며 구한 값이 더 짧을 경우 갱신해줍니다.
따라서 한 번만 제대로 정리를 해주면 되고 재방문은 신경쓰지 않아도 됩니다.
코드를 보며 살펴보겠습니다.
int[][] arr = new int[n + 1][n + 1];
for(int i = 0; i <= n; i++){
Arrays.fill(arr[i], 20000001);
arr[i][i] = 0;
}arr를 n + 1사이즈로 2차원 배열로 선언합니다.
그리고 for문을 이용하여 n까지 탐색하는데, MAX값을 삽입하되 arr[i][i]는 0을 삽입합니다.
같은 노드는 그냥 0을 넣어서 쓸데없는 연산은 하지 않겠다는 뜻입니다.
이후
for(int i = 0; i < fares.length; i++){
int start = fares[i][0];
int end = fares[i][1];
int cost = fares[i][2];
arr[start][end] = arr[end][start] = cost;
}fares크기만큼 for문을 돌텐데, fares[i][0]은 start, [i][1]은 end, [i][2]는 cost로 받아옵니다.
이 때 start는 fares의 시작 지점, end는 도착 지점인데요.
start에서 end 갈때에 cost비용이 들지만 end지점에서 start까지도 cost만큼의 비용이 들기 때문에 arr[start][end] = arr[end][start] = cost입니다.
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int k = 1; k <= n; k++){
arr[j][k] = Math.min(arr[j][k], arr[j][i] + arr[i][k]);
}
}
}여기서 가장 중요한데요.
제일 밖의 for문은 n번 반복하는 경유지점이라고 하겠습니다.
그리고 j와 k는 출발지점과 끝지점이라고 해보겠습니다.
arr[j][k]는 j -> i -> k 로 거쳐가는 것과 j - > k로 바로 가는 것 중 더 작은 값을 가져야 합니다.
따라서 Math.min함수로 간단히 나타낼 수 있습니다.
이후는 간단합니다.
int answer = Integer.MAX_VALUE;
for(int i = 1; i <= n; i++)
answer = Math.min(answer, arr[s][i] + arr[i][a] + arr[i][b]);
return answer;answer = Integer.MAX_VALUE라고 할 때 n번 루프 돌려서 s지점에서 a와 b지점에 도착하기 위한 arr[s][i] + arr[i][a] + arr[i][b]를 찾습니다.
가장 최소값을 answer에 담아서 리턴하면 그것이 정답이 되겠습니다.
* 다익스트라
import java.util.*;
class Edge implements Comparable<Edge>{
int a;
int b;
public Edge(int a, int b){
this.a = a;
this.b = b;
}
@Override
public int compareTo(Edge o){
return this.b - o.b;
}
}
class Solution {
static ArrayList<Edge>[] list;
public static int solution(int n, int s, int a, int b, int[][] fares) {
list = new ArrayList[n + 1];
for (int i = 1; i < list.length; i++) {
list[i] = new ArrayList<>();
}
for (int[] fare : fares) {
int x = fare[0];
int y = fare[1];
int z = fare[2];
list[x].add(new Edge(y, z));
list[y].add(new Edge(x, z));
}
int[] start = new int[n + 1];
int[] startA = new int[n + 1];
int[] startB = new int[n + 1];
Arrays.fill(start, Integer.MAX_VALUE);
Arrays.fill(startA, Integer.MAX_VALUE);
Arrays.fill(startB, Integer.MAX_VALUE);
dijkstra(s, start);
dijkstra(a, startA);
dijkstra(b, startB);
int answer = Integer.MAX_VALUE;
for (int i = 1; i < start.length; i++)
answer = Math.min(answer, start[i] + startA[i] + startB[i]);
return answer;
}
public static void dijkstra(int s, int[] arr) {
arr[s] = 0;
PriorityQueue<Edge> queue = new PriorityQueue<>();
queue.offer(new Edge(s, 0));
while (!queue.isEmpty()) {
Edge now = queue.poll();
for (Edge i : list[now.a])
if (arr[i.a] > now.b + i.b) {
arr[i.a] = now.b + i.b;
queue.offer(new Edge(i.a, arr[i.a]));
}
}
}
}다익스트라 알고리즘을 이용하여 풀이해보겠습니다.
static ArrayList<Edge>[] list;제일먼저, ArrayList를 Edge 라는 클래스를 제네릭으로 받아와서 제네릭 클래스를 생성할 것입니다.
이걸 하는 이유는, 하나의 노드에 대해 여러 개의 간선이 존재할 수 있는데, 제네릭 클래스를 이용하여 하나의 인덱스에 여러 개의 인덱스들을 삽입하고 싶기 때문입니다.
즉, 1과 연결된 노드가 3, 5, 7이 있다면 ArrayList<Edge>타입의 list는 list[1]에서 3, 5, 7이라는 ArrayList를 가지는 것입니다.
한마디로 배열 형태를 띈 ArrayList라고 생각하시면 되겠습니다.
이를 제대로 사용하기위해 제일 먼저 list의 크기를 지정해주어야 하는데요.
list = new ArrayList[n + 1];다음과 같이 나타낸다면 list의 크기는 n + 1크기를 가짐을 알 수 있습니다.
for (int i = 1; i < list.length; i++) {
list[i] = new ArrayList<>();
}이후 list의 각 인덱스마다 모두 ArrayList타입임을 선언해야 하기 때문에 for문을 이용하여 list를 생성합니다.
이를 통해 1번부터 n번까지의 list[i]들은 모두 ArrayList타입이 됩니다.
for (int[] fare : fares) {
int x = fare[0];
int y = fare[1];
int z = fare[2];
list[x].add(new Edge(y, z));
list[y].add(new Edge(x, z));
}이후 입력 받은 fares라는 2차원 배열을 통해 향상된 for문을 이용하여 x, y, z라는 변수를 list에 저장할 것입니다.
다익스트라 알고리즘도 플로이드-와샬 알고리즘처럼 기본적으로 노드와 노드 사이를 값으로 초기화 시켜주어야 합니다.
이 부분까지는 플로이드-와샬과 똑같이 진행됩니다.
이후 배열을 3개 선언합니다.
int[] start = new int[n + 1];
int[] startA = new int[n + 1];
int[] startB = new int[n + 1];
Arrays.fill(start, Integer.MAX_VALUE);
Arrays.fill(startA, Integer.MAX_VALUE);
Arrays.fill(startB, Integer.MAX_VALUE);start배열은 시작점에서 임의으 경유지까지, startA는 a점에서 경유지까지, startB는 b점에서 경유지까지의 경로를
담는 배열입니다.
제일 먼저 값을 초기화 해주어야 하는데, 우리는 각 노드사이의 거리를 최초에는 모른다는 것을 가정하기 때문에
MAX_VALUE를 넣어주어야 합니다.
이후 본격적으로 탐색이 진행됩니다.
dijkstra(s, start);
dijkstra(a, startA);
dijkstra(b, startB);public static void dijkstra(int s, int[] arr) {
arr[s] = 0;
PriorityQueue<Edge> queue = new PriorityQueue<>();
queue.offer(new Edge(s, 0));
while (!queue.isEmpty()) {
Edge now = queue.poll();
for (Edge i : list[now.a])
if (arr[i.a] > now.b + i.b) {
arr[i.a] = now.b + i.b;
queue.offer(new Edge(i.a, arr[i.a]));
}
}
}dijkstra함수의 구조는 간단합니다.
받아온 start[], startA[], startB[]의 배열을 arr로 잡고 최초의 받아온 출발 지점을 s로 잡아서 arr[s] = 0을 삽입합니다.
이후 우선순위 큐를 선언하는데 함수가 총 세번 실행되니 queue도 총 세 번 초기화 되어서 생성됩니다.
왜인지 아시지요? (queue를 초기화 시킨 상태에서 진행해야 하기 때문입니다.)
그렇담 이 queue는 왜 우선순위큐를 사용해야할까요?
단순히 저희는 연결되어 있는 간선을 찾는 것이 목적이 아니라 간선간의 비용 합이 최소가 되는 것을 찾아야 합니다.
Edge제네릭 클래스의 큐에 들어갈 요소들을 살펴보면 각각 (도착지점, 비용)이 될텐데 막무가내로 값들을 다 더하지 않고
비용이 최소가 되는 점들로 미리 정렬을 한 상태에서 도착지점을 찾는 것이 훨씬 수월하고 미래에 불필요한 탐색을 줄여줍니다.
코드를 보며 일단 Edge클래스가 Comparable 인터페이스를 사용할 때 정렬을 살펴보겠습니다.
class Edge implements Comparable<Edge>{
int a;
int b;
public Edge(int a, int b){
this.a = a;
this.b = b;
}
@Override
public int compareTo(Edge o){
return this.b - o.b;
}
}지난 포스팅에도 참 많이 썼던 구문들입니다.
이렇게 작성하시면 this생성자를 통해 오버로딩할 수 있으며 compareTo라는 메서드를 불러와 return 값이 +이면
오름차순, -이면 내림차순을 의미하도록 설계할 수 있습니다.
이렇게 작성하시면 오름차순으로 정렬됩니다.
queue.offer(new Edge(s, 0));그러므로 Queue에는 시작점과 0을 삽입하여 최초의 노드를 굴려가며 탐색을 진행해보도록 하겠습니다.
while (!queue.isEmpty()) {
Edge now = queue.poll();
for (Edge i : list[now.a])
if (arr[i.a] > now.b + i.b) {
arr[i.a] = now.b + i.b;
queue.offer(new Edge(i.a, arr[i.a]));
}
}while문을 통해 queue가 비지 않도록 주의해주시고 Edge의 now는 queue의 자동 정렬된 최소 비용의 노드가 선택되어 담깁니다.
이 때 향상된 for문을 이용하여 list에서 가져온 now의 a라는, 최초의 1과 연결된 list들을 각각 찾아서 for문을 돌립니다.
arr[i.a]가, 그러니까 최초에 Integer_MAX_VALUE로 삽입했던 그 값이 만약 최초에 삽입된 1의 비용과 i번 노드의 비용과 더했을 때 크다면(최초엔 당연히 큽니다.) arr[i.a] = now.b + i.b;로 갱신합니다.
이후 queue에는 새로운 노드를 찾았으므로 i.a를 삽입하고 비용은 arr[i.a]가 되게됩니다.
이 반복을 계속해서 하게되면 결국 start지점에서 갈 수 있는 모든 노드의 값이 arr에 담기게 되고 결과적으로 start배열에 담기게 됩니다.
이 start배열과 마찬가지로 startA와 startB배열도 똑같이 시행해주시고 그 결과 s -> 어느 지점 i까지의 결과와
a 지점에서 i지점까지의 결과, b지점에서 i지점까지의 비용을 담은 arr배열을 생성하게 됩니다.
이후
for (int i = 1; i < start.length; i++)
answer = Math.min(answer, start[i] + startA[i] + startB[i]);
return answer;for문을 이용하여 어느 i지점에서 경유해서 가는지를 더한 최소값을 리턴해주면 정답이 되는 것을 확인할 수 있게됩니다.
결과적으로 보면 플로이드-와샬보다 다익스트라가 더 까다로워보이지만 시간복잡도는 훨씬 더 효율적입니다.
n값이 커지면 커질수록 삼중for문에 대한 부담감이 커지기 때문이라고 전 생각합니다.
여러분들은 어떤 알고리즘이 더 쉬우셨나요?
감사합니다.
'프로그래머스 문제 풀이' 카테고리의 다른 글
| 프로그래머스 코딩테스트 연습 - 양과 늑대 (DFS, 이진 탐색 트리) (0) | 2022.07.22 |
|---|---|
| 프로그래머스 코딩테스트 연습 - 가장 먼 노드 (다익스트라, 플로이드-와샬, DFS) (0) | 2022.07.20 |
| 프로그래머스 코딩테스트 연습 - 기둥과 보 설치 (구현) (0) | 2022.07.16 |
| 프로그래머스 코딩테스트 연습 - 불량 사용자 (백트래킹, 정규식) (0) | 2022.07.12 |
| 프로그래머스 코딩테스트 연습 - 자물쇠와 열쇠 (구현, 배열) (0) | 2022.07.09 |
