백준 No.1719 택배 - JAVA

문제

명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로르 거쳐야 하는지 결정하지 못했다. 어떤 경로를 거칠지 정해서, 이를 경로표로 정리하는 것이 여러분이 할 일이다.

예시된 그래프에서 굵게 표시된 1,2,3,4,5,6은 집하장을 나타낸다. 정점간의 간선은 두 집하장간에 화물 이동이 가능함을 나타내며, 가중치는 이동에 걸리는 시간이다. 이로부터 얻어내야 하는 경로표는 다음과 같다.

경로표는 한 집하장에서 다른 집하장으로 최단경로로 화물을 이동시키기 위해 가장 먼저 거쳐야 하는 집하장을 나타낸 것이다. 예를 들어 4행 5열의 6은 4번 집하장에서 5번 집하장으로 최단 경로를 통해 가기 위해서는 제일 먼저 6번 집하장으로 이동해야 한다는 의미이다.

6 10
1 2 2
1 3 1
2 4 5
2 5 3
2 6 7
3 4 4
3 5 6
3 6 7
4 6 4
5 6 2

 

처음에 인접리스트로 접근을 시도했는데 접근자체가 어려워서 결국 풀이를 찾아봤는데 플로이드와샬이라는 알고리즘으로 푸는 방법들이 많았고 확시히 코드 자체가 간결하게 풀 수 있어 이에대해 학습해봤다.

 

플로이드 와샬

 

다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택해야 했다면 플로이드 와샬은 알고리즘은 기본적으로 거쳐가는 정점을 기준으로 알고리즘을 수핸한다는 점에서 특징이 있다

플로이다 와샬 알고리즘의 핵심 아이디어는 '거쳐가는 정점'을  기준으로 최단 거리를 구하는 것이다

 

출처 겸 정리가 잘 되어 있는 블로그,

https://blog.naver.com/ndb796/221234427842

24. 플로이드 와샬(Floyd Warshall) 알고리즘

 

 

일단 위 알고리즘을 이해하고 풀이를 보면

플로이드 와샬 알고리즘은 일단 2차원 배열을 통해 모돈 정점에서부터 모든 정점까지의 최단 경로를 구하는 것인데 여기서 2차원 배열에 주어진 입력값을 바탕으로 2차원 배열이 만들어지고 해당 배열들은 1일때, 2일떄 ...N 이런식으로 계속해서 변경해간다. 이 과정은 if문으로 걸러줘야 하는데 조건은 D(i,j) >D(i,K)+D(K,J)   이런식을 통해 걸러줘야 한다. 해당 식을 숫자로 보면 2에서 3으로 가는 최단 경로를 구해야하는데 2에서 3으로 바로 가는게 빠르냐 아니면 다른 곳곳인 k를 거쳐 가는게 빠르냐고 묻는 것이다. 해당 if문을 지난다는 건 거쳐 가는게 빠른게 아닌 바로 가는게 더 빠르다는 것이다.

 

해당 문제에서 graph를 2차원 배열로 받고 2차원 배열을 전부 일단 가장 큰 최댓값으로 초기화한다. (여기서 Integer.MAX_VALUE는 안된다 - 해당 값으로 계산을 해야하기 떄문에) 전부 값을 채운다음 입력 값들을 채워넣는다.

graph[start][end] = graph[end][start] = Math.min(graph[start][end],cost);

이렇게 구성한다면 문제에서 예제로 주어진 식을 예로든다면 2,3에 들어가는 값은 무엇일까?

바로 최댓값(INF)값이 들어간다. 왜냐하면 2 정점에서 3정점으로 바로 연결된 간선이 없기 때문이다. 그렇다면 2정점에서 1로 가는 간선, 1에서 3으로 가는 간선은 존재한다. 이런 경우 최단 경로를 구한 것이다.

왜 처음에 최대값으로 초기화했는지가 여기서 밝혀진다. 해당 값이 만일 두 간선을 더했을 경우보다 작은값이라면 최단 경로를 구할 수 없었을 것이다. 

식으로 본다면

graph[2][3] > graph[2][1] + graph[1][3]

값으로 본다면 (INF가 10000일 경우)  10000 > 2 + 1 이므로 if문에서 이를 통과하여 해당 위치에 3이 들어가면된다. 이런식으로 계속해서 순회하는게 해당 알고리즘에 핵심인듯하다. 만약 현재 값이 더 작다면 해당 값을 변경할 필요가 없다.

 

1. 모든 배열을 최댓값 넣기

2. 주어진 입력값을 통해 가중치로 변경한다. -> 여기서 연결이 안 된 값들은 값을 변경하지 않으므로 최댓값

3. 플로이드 아샬 알고리즘에 핵심 -> 

graph[j][k] = Math.min(graph[j][i] + graph[i][k], graph[j][k]);

여기서 해당 문제는 어떻게 풀까?

 

해당 문제는 결국 최단 경로를 가기 전에 어디를 방문하는지를 알아야 하는 문제이다.

 

 4행 5열의 6은 4번 집하장에서 5번 집하장으로 최단 경로를 통해 가기 위해서는 제일 먼저 6번 집하장으로 이동해야 한다는 의미이다.

해당 말이 해답이다. 

4 정점에서 5정점을 가려면 6을 거쳐야 한다.

graph[4][5]  > graph[4][6] + graph[6][5] 가 성립한다는 소리이다. 그렇다면 4,6이 6이면 되는 것이다.

그렇기에 dist 배열을 하나 더 만든다. 여기서 dist배열은 다음 노드가 어떤 값을 가르키는지 정리하기 위한 배열이다.

dist

for (int i = 1; i < N+1 ; i++) {
    for (int j = 1; j < N+1 ; j++) {
        dist[i][j] = j;
    }
}

 

 

이렇게 초기화하면 123456 이 계속 반복할 것이다. dist[4][6] 은 6이라는 소리다. 

그렇다면

dist[4][5] = dist[4][6] 을 넣으면 된다. (4정점에서 5정점을 갈때 6을 거쳐서 갔다는 소리임)

 

for (int i = 1; i < N+1 ; i++) {
    for (int j = 1; j < N+1; j++) {
        if(i == j){
            System.out.print("- ");
        }else{
            System.out.print(dist[i][j]+" ");
        }
    }
    System.out.println();
}

그리고 문제에서 원하는대로 값을 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.function.IntBinaryOperator;

public class Main {

    static int N,M;


    public static void main(String[] args) throws IOException {
        BufferedReader br  =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        int graph[][] = new int[N+1][N+1];
        int dist[][] = new int[N+1][N+1];


        for (int i = 0; i < N + 1 ; i++) {
            Arrays.fill(graph[i],Integer.MAX_VALUE/2);
        }

        for (int i = 1; i < N+1 ; i++) {
            for (int j = 1; j < N+1 ; j++) {
                dist[i][j] = j;
            }
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            graph[start][end] = graph[end][start] = Math.min(graph[start][end],cost);
        }


        for (int i = 1; i < N+1; i++) {
            for (int j = 1; j <N+1 ; j++) {
                for (int k = 1; k <N+1 ; k++) {
                    if(graph[j][k] > graph[j][i]+graph[i][k]) {
                        graph[j][k] = Math.min(graph[j][i] + graph[i][k], graph[j][k]);
                        dist[j][k] = dist[j][i];
                    }
                }
            }
        }

        for (int i = 1; i < N+1 ; i++) {
            for (int j = 1; j < N+1; j++) {
                if(i == j){
                    System.out.print("- ");
                }else{
                    System.out.print(dist[i][j]+" ");
                }
            }
            System.out.println();
        }

    }
}