[프로그래머스] 2021 카카오 / 합승 택시 요금 (Java)

#4 합승 택시 요금

2021 카카오 블라인드

난이도 : LEVEL 3

유형 : 그래프 탐색/ 다익스트라 / 플로이드 와샬

코딩테스트 연습 - 합승 택시 요금

[문제]

밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다. "무지"는 자신이 택시를 이용할 때 동료인 어피치 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을 알게 되었습니다. "무지"는 "어피치"와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 있을 지 계산해 보고 "어피치"에게 합승을 제안해 보려고 합니다.

위 예시 그림은 택시가 이동 가능한 반경에 있는 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로 가는 경로가 존재하는 경우만 입력으로 주어집니다.

 

 

 

문제 풀이 

해당 문제의 본질은 다익스트라 최단경로 알고리즘이다. 

 

두 최단경로 그래프 알고리즘의 차이는 아래와 같다.

• Dijkstra 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.
  • 특정 경로에 대한 최단 경로를 구하려면 Dijkstra (우선순위 queue사용)

• 그에 반해 Floyd Warshall 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다.
  • 모든 경로에 대한 최단 경로를 구하려면 Floyd Warshall

 

구상

1. s, a, b에 대한 최단경로를 각각 구한다. - 다익스트라 
2. 1번에서 구한 최단경로 데이터를 가지고 (a와 b가 동행한 비용) + (a와 b 각각 각자의 집으로 간 비용)의 최소비용을 찾는다. - 플로이드와샬 

 

스케치

1번 로직

a와 b에서 다른 모든 정점의 최단경로는 s로 가는 최단 경로를 찾을 때 쓰이고 s에 대한 다른 모든 정점의 최단경로는 a와 b가 s에서 자신의 집으로 귀가할 최단 경로를 찾는데 쓰일 것이다. 우선순위큐를 사용한 BFS탐색을 통해 다익스트라 알고리즘을 구현해주면 된다. 

 

2번 로직

1번로직에서 구한 3가지의 최단 경로 데이터를 통해  1번 ~ n번의 지점까지 모두 조회하여 동행 최단 경로를 구하면 된다. 만약 세개의 경로 중 한 개라도 경로가 없을 경우에는 패스해주자. 그리고 [제한사항]을 보면 경로가 존재하는 경우만 입력으로 주어진다고 했기 때문에 아예 존재하지 않을 경우에 대한 예외처리는 안해줘도 될 것 같다.

 

구현

1번 로직 코드

원래 기본 다익스트라 알고리즘은 dp 1차 배열을 사용하지만 나는 flag란 변수를 추가하여 2차 배열을 사용했다. 그리고나서 각 최단 경로에 대한 데이터를 flag를 통해 분산시켰다. 

• flag : 0 → s의 최단경로 데이터 저장
• flag : 1 → a의 최단경로 데이터 저장
• flag : 2 → b의 최단경로 데이터 저장

// s의 최단경로 (a+b)동승 dp[route][0] 
dijkstra(s,0);

// a집에서의 최단 경로 dp[route][1]
dijkstra(a,1);

// b집에서의 최단 경로 dp[route][2]
dijkstra(b,2);


// 특정경로 조회 : dijkstra -> s,a,b 각각 
static void dijkstra(int start, int flag) {
	Queue<Node> q = new PriorityQueue<>();
	Arrays.fill(checked, false);

	q.add(new Node(start,0));

	dp[start][flag] =0;

	while(!q.isEmpty()) {
		Node node = q.poll();
		int to = node.to;

		if(checked[to]) continue;
		else checked[to] = true;

		for(Node node2 : list[to]) {
			int next = node2.to;
			int value = node2.value;
			if(dp[next][flag] >= dp[to][flag] + value) {
				dp[next][flag] = dp[to][flag] + value;
				q.add(new Node(next, dp[next][flag]));
			}
		}
	}
}

class Node implements Comparable<Node>{
	int to;
	int value;
	
	public Node(int to, int value) {
		this.to = to;
		this.value = value;
	}

	@Override
	public int compareTo(Node o) {
		return this.value - o.value;
	}
}

 

 2번 로직 코드

(a와 b가 동행한 비용) + (a와 b 각각 각자의 집으로 간 비용)을 구하면 된다.

 

최솟값은 a,b 동행없이 각자 집으로가는 최단 비용으로 잡는다.

int noShare = dp[s][1] + dp[s][2]; // a,b 동행없이 각자 집으로가는 최단 비용

 

k  →     i      → j

s  →  동행(i)  → a집

                      → b집

☛ 이제 여기서 중간에 i 경로를 넣어서 동행하면 더 최단 비용이 나오는지 탐색해주면 된다.

 

ex)  start =4, a= 6, b=2

start지점에서의 각 노드 최단경로를 s[] = dp[][0] 에 저장

A 지점에서의 각 노드 최단경로를 a[] = dp[][1] 에 저장

B 지점에서의 각 노드 최단경로를 b[] = dp[][2] 에 저장

→ 편하게 각 배열을 s[], a[], b[]라고 칭하자.

 

그럼 s[1] + a[1] + b[1]의 값은 무엇을 나타낼까?

s[1] : 4(start)→ 1 까지 a와 b가 동행한 비용

a[1] : 1 → 6(a집) 까지 a가 지불한 비용

b[1] : 1 → 2(b집) 까지 b가 지불한 비용

(방향이 없는 그래프라서 6→1 , 1→6의 비용 같음)

 

따라서, s[i]는 4(start)에서 i까지의 최단 비용,

           a[i]는 6(a집)에서 i까지의 최단 비용 ,

           b[i]는 2(b집)에서 i까지의 최단 비용 을 나타낸다.

int noShare = dp[s][1] + dp[s][2];

// 동행 최단 경로 구하기
// dp[route][0] + dp[route][1] +dp[route][2]
// -> route까지 동행 후 각자 집으로 가는 비용
int minCost = noShare;
for(int i=1; i<n+1; i++) {
	// 셋 중 하나의 경로라도 길이 없으면 pass
	if(dp[i][0] ==MAX || dp[i][1] ==MAX  || dp[i][2] ==MAX ) continue;
	minCost = Math.min(minCost, dp[i][0] + dp[i][1] + dp[i][2]);
}

 

 

전체 풀이 코드

import java.util.*;

class Solution {
	static List<Node>[] list;
	static int[][] dp;
	static int MAX = Integer.MAX_VALUE;
	static boolean[] checked;
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
            
	        list = new ArrayList[n+1];
	        dp = new int[n+1][3];
	        checked = new boolean[n+1];
	        for(int i=0; i<list.length; i++) {
	        	list[i] = new ArrayList<>();
	        }
	        for(int i=0; i<n+1; i++	) {
	        	Arrays.fill(dp[i], MAX);
	        }
	        
	        for(int i =0; i<fares.length; i++) {
	        	int start = fares[i][0];
	        	int end = fares[i][1];
	        	int value = fares[i][2];
	        	
	        	
	        	list[start].add(new Node(end, value));
	        	list[end].add(new Node(start, value));
	        }
	        
	        // s의 최단경로 (a+b)동승 dp[route][0] 
	        dijkstra(s,0);
	        
	        // a집에서의 최단 경로 dp[route][1]
	        dijkstra(a,1);
	        
	        // b집에서의 최단 경로 dp[route][2]
	        dijkstra(b,2);
	     
        
	        int noShare = dp[s][1] + dp[s][2];
	        
	        // 동행 최단 경로 구하기
	        // dp[route][0] + dp[route][1] +dp[route][2]
	        // -> route까지 동행 후 각자 집으로 가는 비용
	        int minCost = noShare;
	        for(int i=1; i<n+1; i++) {
	        	if(dp[i][0] ==MAX || dp[i][1] ==MAX  || dp[i][2] ==MAX ) continue;
	        	
	        	minCost = Math.min(minCost, dp[i][0] + dp[i][1] + dp[i][2]);
	        }
	        
	        
	        return minCost;
    }
	// 특정경로 조회 : dijkstra -> s,a,b 각각 
	static void dijkstra(int start, int flag) {
		 Queue<Node> q = new PriorityQueue<>();
		 Arrays.fill(checked, false);
		 
		 q.add(new Node(start,0));
		 
		 dp[start][flag] =0;
		 
		 while(!q.isEmpty()) {
			 Node node = q.poll();
			 int to = node.to;
			 
			 if(checked[to]) continue;
			 else checked[to] = true;
			 
			 for(Node node2 : list[to]) {
				 int next = node2.to;
				 int value = node2.value;
				 if(dp[next][flag] >= dp[to][flag] + value) {
					 dp[next][flag] = dp[to][flag] + value;
					 q.add(new Node(next, dp[next][flag]));
				 }
			 }
		 }
	 }
}

class Node implements Comparable<Node>{
	int to;
	int value;
	
	public Node(int to, int value) {
		this.to = to;
		this.value = value;
	}

	@Override
	public int compareTo(Node o) {
		return this.value - o.value;
	}
}