[프로그래머스/자바] 합승 택시 요금 풀이 - 2021 KAKAO BLIND RECRUITMENT

https://school.programmers.co.kr/learn/courses/30/lessons/72413

프로그래머스

 

2021 KAKAO BLIND RECRUITMENT Level 3 문제다.

 

 

처음엔 정확성 테스트만 있는 줄 알고

제일 익숙한 DFS로 풀었었다.

하나의 DFS 메소드에서 합승하는 경우, a 혼자 가는 경우, b 혼자 가는 경우 각각 나눠 재귀함수를 호출했었고

정확성은 다 맞았지만 효율성에서 틀렸었다..ㅎ

↓ DFS로 구현한 코드 

import java.util.*;

class Solution {
    static int INF = 20000001;
    static int min = INF;
    static boolean[] visit;
    static ArrayList<int[]> list[];
    static int A, B;
    static int aCost, bCost;
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        visit = new boolean[n + 1];
        list = new ArrayList[n + 1];
        
        A = a;
        B = b;
        
        for(int i=1;i<=n;i++)
            list[i] = new ArrayList<>();
        
        for(int i=0;i<fares.length;i++) {
            int start = fares[i][0];
            int end = fares[i][1];
            int cost = fares[i][2];
            
            list[start].add(new int[] {end, cost});
            list[end].add(new int[] {start, cost});
        }
        
        visit[s] = true;
        DFS('t', 0, s);
        
        return min;
    }
    
    static void DFS(char type, int cost, int now) {
        if(type == 'a' && now == A) {
            aCost = Math.min(aCost, cost);
            return;
        }
        if(type == 'b' && now == B) {
         bCost = Math.min(bCost, cost);
         return;
        }
        if(type == 't') {
         aCost = bCost = INF;
         DFS('a', 0, now);
         DFS('b', 0, now);
         min = Math.min(min, cost + aCost + bCost);
        }
        
        for(int arr[] : list[now]) {
         int next = arr[0];
         int c = arr[1];
        
            if(!visit[next]) {
                visit[next] = true;
                DFS(type, cost + c, next);
                visit[next] = false;
            }
        }
        
    }
}

 

그래프가 주어지고 최단 거리를 구하는 문제이므로

플로이드 워셜 알고리즘으로 풀었다.

 

fares를 탐색해 그래프를 나타내는 배열 arr를 생성해준다.

경로가 존재하지 않을 경우 INF, 자기 자신으로 가는 경우는 0으로 초기화해 준다.

INF는 최대지점갯수 200 * 최대요금 100000 + 1인 20000001로 설정했다.

 

		for(int k=1;k<=n;k++)
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					if(arr[i][j] > arr[i][k] + arr[k][j])
						arr[i][j] = arr[i][k] + arr[k][j];

플로이드 워셜(i->j가는 경로보다 i->k->j가는 경로가 더 비용이 적다면 갱신)을 위와 같이 수행하고

 

		// s에서 i까지 합승 후 각자 a와 b로 가는 경우
		for(int i=1;i<=n;i++)
			min = Math.min(min, arr[s][i] + arr[i][a] + arr[i][b]);

경로 모두를 고려해 가장 최소가 되는 비용을 찾는다.

즉, 시작점 s에서 i까지 합승한 후(arr[s][i]) i에서 각자 목적지로 가는 경우 (arr[i][a], arr[i][b])가 된다.

i가 시작점 s와 같은 경우 (arr[s][s])는 0이므로 합승하지 않고 각자 가는 경우도 포함된다.

 

 

- 배운점 및 느낀점

플로이드 워셜은 O(N^3)이기 때문에 시간 초과가 날까 조마조마하면서 제출했지만,

다행히 다 맞았고 시간을 더 줄이기 위해서는 다익스트라로 풀어야 할 것 같다.

무조건 익숙한 DFS나 BFS로 접근하기 보다는 효율성을 생각하며 알고리즘을 선택해야겠다.

다음엔 다익스트라로도 풀어보기!

 

 

import java.util.*;

class Solution {
    static final int INF = 20000001;
    public int solution(int n, int s, int a, int b, int[][] fares) {
		int[][] arr = new int[n + 1][n + 1];

		for(int i=1;i<=n;i++) {
			Arrays.fill(arr[i], INF);
			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] = cost;
			arr[end][start] = cost;
		}

		for(int k=1;k<=n;k++)
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					if(arr[i][j] > arr[i][k] + arr[k][j])
						arr[i][j] = arr[i][k] + arr[k][j];

		int min = INF;

		// s에서 i까지 합승 후 각자 a와 b로 가는 경우
		for(int i=1;i<=n;i++)
			min = Math.min(min, arr[s][i] + arr[i][a] + arr[i][b]);

		return min;
    }
}