2021 KAKAO BLIND RECRUITMENT - 합승 택시 요금

using Java 11

"합승 택시 요금" 문제 보기

import java.io.*;
import java.util.*;
public class Solution {
	public static ArrayList<ArrayList<Node>> map = new ArrayList<>();
	public static boolean[] visited;
	public static int[] fare;
	public static class Node implements Comparable<Node>{
		int to;
		int fare;
		public Node(int to, int fare) {
			this.to = to;
			this.fare = fare;
		}
		
		@Override
		public int compareTo(Node o) {
			return this.fare- o.fare;
		}
	}
	public static int getFare(int start, int s, int a, int b) {
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(start, 0));
		fare[start] = 0;
		while(!pq.isEmpty()) {
			Node curNode = pq.poll();
			int next = curNode.to;
			if(!visited[next]) {
				visited[next] =  true;
				ArrayList<Node> arr = map.get(next);
				for(int i = 0; i < arr.size(); i++) {
					Node tmp = arr.get(i);
					if(fare[tmp.to] > tmp.fare + fare[next]) {
						fare[tmp.to] = tmp.fare + fare[next];
						pq.add(new Node(tmp.to, fare[tmp.to]));
					}
				}
				
			}
		}
		return fare[s] + fare[a] + fare[b];
	}
	public static int solution(int n, int s, int a, int b, int[][] fares) {
		for(int i = 0; i <= n; i++) {
			map.add(new ArrayList<>());
		}
		for(int i = 0; i < fares.length; i++) {
			map.get(fares[i][0]).add(new Node(fares[i][1], fares[i][2]));
			map.get(fares[i][1]).add(new Node(fares[i][0], fares[i][2]));
		}
		int min = Integer.MAX_VALUE;
		for(int i = 1; i <= n; i++) {
			visited = new boolean[n+1];
			Arrays.fill(visited, false);
			fare = new int[n+1];
			Arrays.fill(fare, 1000001);
			int result = getFare(i, s, a, b);
			if(result < min) min = result;
		}
		return min;
	}
}

📍 다익스트라 사용

일단 아이디어를 내는 게 좀 어려웠다.
중간 지점을 거쳐가는 최단 경로 문제는 다익스트라 두 번으로 해결하는게 보통이니까 비슷한 방법으로 해결하려고 했는데 그게 아니었다. (어찌보면 비슷하긴 하지만)

⁉️ 처음 생각한 방법
중간 지점(합승 구간)을 노드 m 이라하면
s -> m, m -> a, m -> b 의 최단 경로를 찾으면 되는데
m의 범위는 1 <= m <= n 이 되기 때문에 3 * n 번 다익스트라를 수행 해야 한다.

딱 봐도 효율성 테스트를 통과 못 할 거 같았다. 그리고 역시나 효율성 시간 초과가 우수수수수수 떴다.ㅎㅎ 그래서 구글링을 좀 했다.
다익스트라로 계산하면 시간 초과가 나니까 플로이드 외샬 알로리즘으로 풀어야한단다... 음 근데 이상한 고집인지 뭔지 다익스트라로 풀고 싶었다. 그래서 꽤 오래 아이디어 고민을 해봤다.

‼️ 거꾸로 생각하자
문제를 다시 읽다보니 주어진 map이 undirected graph라 양방향으로 비용이 똑같다는 점이 눈에 들어왔다. 여기에 의도가 있을 거라고 생각해서 반대 방향으로 탐색하는 방법을 생각해봤다.

출발지를 중간 지점 m 으로 설정하고 최단 경로를 구하면 m -> s, m -> a, m -> b 최단 경로가 한번에 구해진다.
이 세개를 그냥 더하면 되는 거였다. (s -> m 이랑 비용이 똑같기 때문에!)
합승을 안하는 경우는 m == s 일때로 구해지기 때문에 모든 조건을 검사할 수 있다.

즉, 시작점을 1부터 n까지로 n번 최단 경로를 구하고 구할 때마다 dist[s] + dist[a] + dist[b] 값을 반환해 최소값을 구해주면 된다. 코드에서는 fare 배열이 dist 배열에 해당한다.

int min = Integer.MAX_VALUE;
for(int i = 1; i <= n; i++) {
	visited = new boolean[n+1];
	Arrays.fill(visited, false);
	fare = new int[n+1];
	Arrays.fill(fare, 1000001);
	int result = getFare(i, s, a, b);
	if(result < min) min = result;
}

📍 dist 배열 초기화

이렇게 고민해서 풀었는데 시간 초과가 났다! (화도 많이 났다.) 효율성 test case 7번 딱 하나만,,, 원인을 모르겠어서 찍어서 수정하고 돌렸는데 정답이란다. 😱 🥶 충격과 공포의 순간 이었다.

다른 문제를 풀때 중간 지점이 있는 다익스트라는 처음 dist 배열을 Integer MAX VALUE로 채워버리면 overflow가 발생한다는 점을 기억했다. (여러 개의 결과를 더하는 경우)
그래서 처음에는 적당한 수 라고 생각한 '10000001'로 설정했다. 그랬더니 결과가 효율성 7번 시간 초과였다. 보통 overflow면 시간 초과가 아니라 "실패"로 떠야하는게 맞는 거 아닌가.

숫자가 커서 연산 속도에 영향을 줄거라고는 생각을 해본적이 없긴 한데 그래도 혹시 설마 그냥 찍어서 '1000001'로 초깃값을 바꿨더니,, 통과했다. ⁉️

그래서 초깃값을 이거저거 변경을 해봤다.
100,001 ❌
1,000,001 ⭕️
10,000,001 ❌ (효율성 7번 테스트만 실패)
100,000,001 ❌ (효율성 7번 테스트만 실패)

Integer.MAX_VALUE / 3 - 1 ⭕️
: 대충 715,827,881 이 정도 되는데, fare[s] + fare[a] + fare[b] 계산 값이 overflow 안 나려면 이 정도 값이면 될 거 같았다.

일정 값 이상에서 계속 시간 초과가 나면 이해 하겠는데 흐음..
구글링을 해봐도 설명해주는 사람이 아무도 없었다. (아시는 분 댓글 부탁드려요ㅠㅠ) 초깃값 설정이 효율성 테스트에 영향을 주기도 하나,, 일정 범위에서 되다 안되다 하니까 알고리즘을 아예 잘못 짰나 싶다.