합승 택시 요금 - 프로그래머스

Yuno·2024년 7월 21일

Java)코테 연습

목록 보기

18/18

사용한 알고리즘 : 프로이드 - 워셜 알고리즘

해당 문제는 최단경로를 찾는것이기 때문에
다익스트라 알고리즘 과 프로이드- 워셜 알고리즘 중에
하나를 선택해야 했다.

🤔프로이드 - 워셜 알고리즘을 선택한 이유는?

기본적으로 다익스트라 알고리즘이 단일 시작점에서 다른 노드까지의 최단 경로를 찾는데 매우 효율 적이다.

다익스트라 알고리즘은 우선순위 큐를 사용하면, 시간복잡도는
$O(E log V)$ 로,
프로이드 - 워셜 알고리즘의 $O(V)^3$ 의 시간복잡도 보다 빠르기 때문이다.
E는 간선의 수, V는 노드의 수

하지만 해당 문제는 합승이 가능한 모든 지점을 거쳐 각각의 목적지 까지의 최단거리를 구하는 것 이었기 때문에 모든 노드들간의 거리를 저장할 필요가 있었다.

저장한 모든 노드들간의 거리를 확인해 최단거리를 리턴하는것이 이번 문제의 목표.

📌 상수와 배열 선언

공통으로 사용될 각 노드들간의 거리를 나타낼 배열 선언
양방향 그래프이지만, 경로가 존재하지 않을수 있어서 final 상수로 나의 임의의 값 설정

해당 그림처럼 연결이 되지 않은 부분(간선이 없는 부분)은 무한대로 설정된다.

final static int INF = 9999999;
static int[][] dist;

📌 프로이드 - 워셜 알고리즘 함수

노드의 갯수 $n$ 과 노드와 간선을 담은 2차원배열을 받은 메서드
거리배열 초기화 후, 자기자신을 제외한 거리는 모두 무한대로 설정
해당 작업으로 자기자신은 모두 0으로 초기화되고 나머지만 무한대가 된다.
n + 1은 직관적으로 알기 쉽게 하기위해 0번 인덱스는 사용하지 않는다. 그러므로 배열의 크기는 하나 더 필요하게 된다.

public static void floydWarshall(int n, int[][] fares) {
    dist = new int[n + 1][n + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i !=j) {
                dist[i][j] = INF;
            }
        }
    }

주어진 요금정보(간선의 값)로 거리 배열 초기화
양방향 도로 이므로, 0과 1을 바꿔 동시에 작업해준다.

for (int[] fare : fares) {
    dist[fare[0]][fare[1]] = fare[2];
    dist[fare[1]][fare[0]] = fare[2];

3중 반복문으로 경유지를 거쳐가는 경로가 존재하면, 최단 거리를 갱신하면서 거리배열을 완성해나간다.

for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dist[i][k] != INF && dist[k][j] != INF) {
                dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

📌 solution 메서드

floydWarshall 메서드에 계산값을 넘겨주고,
해당 문제의 결과값을 무한대로 잡아놓는다.

floydWarshall(n, fares);
int min = INF;

모든 지점을 중간지점으로 고려해서 최소 요금을 계산한다.
if문의 조건은 경로가 존재한다면, 최소 요금 갱신

for (int i = 1; i <= n; i++) {
    if (dist[s][i] != INF && dist[i][a] != INF && dist[i][b] != INF) {
        min = Math.min(min, dist[s][i] + dist[i][a] + dist[i][b]);
    }
}

✏️ 해당 코드 동작 과정

거리 배열 초기화

node	1	2	3	4	5	6
1	0	INF	INF	INF	INF	INF
2	INF	0	INF	INF	INF	INF
3	INF	INF	0	INF	INF	INF
4	INF	INF	INF	0	INF	INF
5	INF	INF	INF	INF	0	INF
6	INF	INF	INF	INF	INF	0

주어진 간선 정보로 거리배열 초기화

node	1	2	3	4	5	6
1	0	INF	INF	INF	INF	25
2	INF	0	22	66	INF	INF
3	41	INF	0	INF	24	INF
4	10	INF	INF	0	INF	50
5	24	INF	INF	INF	0	2
6	INF	INF	INF	INF	INF	0

양방향 이므로 반대 거리도 초기화

node	1	2	3	4	5	6
1	0	INF	41	10	24	25
2	INF	0	22	66	INF	INF
3	41	22	0	INF	24	INF
4	10	66	INF	0	INF	50
5	24	INF	24	INF	0	2
6	25	INF	INF	50	2	0

프로이드 - 워셜 알고리즘으로 최단거리 갱신

node	1	2	3	4	5	6
1	0	63	41	10	24	25
2	63	0	22	66	46	101
3	41	22	0	51	24	26
4	10	66	51	0	34	35
5	24	46	24	34	0	2
6	25	101	26	35	2	0

💻 최종 코드 💻

class Solution {
    final static int INF = 9999999;
    static int[][] dist;

    public static void floydWarshall(int n, int[][] fares) {
        dist = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i !=j) {
                    dist[i][j] = INF;
                }
            }
        }
        for (int[] fare : fares) {
            dist[fare[0]][fare[1]] = fare[2];
            dist[fare[1]][fare[0]] = fare[2];
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (dist[i][k] != INF && dist[k][j] != INF) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }
    }

    public int solution(int n, int s, int a, int b, int[][] fares) {
        floydWarshall(n, fares);
        int min = INF;

        for (int i = 1; i <= n; i++) {
            if (dist[s][i] != INF && dist[i][a] != INF && dist[i][b] != INF) {
                min = Math.min(min, dist[s][i] + dist[i][a] + dist[i][b]);
            }
        }
        return min;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int n = 6;
        int s = 4;
        int a = 6;
        int b = 2;
        int[][] fares = {{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}};
        System.out.println(sol.solution(n, s, a, b, fares));
    }
}

👏👏👏👏👏👏👏👏👏

👉프로이드 - 워셜(Floyd - Warshall) 알고리즘

초기화

그래프의 가중치 행렬을 초기 거리 행렬로 설정
자기 자신으로의 거리는 0으로 설정
직접 연결되지 않은 노드 사이의 거리는 무한대로 설정

동적 프로그래밍(Dynamic Programming)

각 경유지를 시작노드부터 순차적으로 고려
각 노드에서 다른 노드까지의 거리를 또 다른 노드를 거쳐 가는 경로를 통해 거리를 갱신
갱신공식 :
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Yuno

Hello World

이전 포스트