[JAVA][백준 11404] 플로이드

https://www.acmicpc.net/problem/11404

---

풀이 과정

해당 문제는 이름에 대놓고 쓰여있듯이 플로이드-워셜 알고리즘을 이용하여 간단하게 풀 수 있는 문제이다.

그런데 플로이드 워셜 알고리즘 공부한지가 오래되어서 다시 공부할 겸 풀어볼려고 한다.

 

플로이드 워셜 알고리즘을 대충 기억하고 있는 사람의 눈으로 이 문제를 봤을때

n개의 도시와 한 도시에서 출발해서 다른 도시에 도착하는 m개의 버스가 있는데 각 버스마다 비용이 다르고...

모든 도시의 쌍(a, b)에 대해서 a->b로 가는데 필요한 비용의 최솟값을 구해야한다..

뭔가 배열에 최솟값을 계속 갱신해나가는 형태인 것 같다.

 

 

일단 입력을 받고 생각해보려고 했는데

입력값이 a->b로가는 비용이 들어오는 형태라서

입력을 받으면서 갱신하는 방식이 좀 더 효율적인 것 같다.

비용을 저장할 n * n배열을 만들고 주어진 노선의 비용을 최소값으로 갱신하면 될 것 같다.

 

최소값을 찾아야 하므로 모든 배열을 int의 최댓값으로 설정하고 시작!

 

코드를 아래와 같이 작성하고 결과를 출력해봤는데

 

갱신이 덜 됐다.

생각해보니 바로 a->b로 가는 직접 연결된 노선만 갱신을 한거고 버스를 갈아탔을때 발생할 수 있는 비용도 갱신을 해줘야된다.

어떻게 갈아타는 비용을 고려할까?

 

갱신이 많이 안되어있는 2번 도시를 보면 어딘가 경유해서 1번, 3번, 5번 가는 최소비용을 구해야한다.

2번에서 갈 수 있는 도시는 4번 도시가 유일하다.

4번 도시에서 갈 수 있는 도시는 5번 도시.

그럼 2번 -> 5번으로 가는 비용은 2->4로가는 비용(2) + 4->5로가는 비용(3) = 5로 갱신을 해야한다.

그럼
2147483647 0 2147483647 2 2147483647 
-> 2147483647 0 2147483647 2 5

이런 형태로 바뀔 것이고 2 -> 5 -> 1 도 구할 수 있다.

 

이걸 코드로 변환하기 위해 생각을 해보면,
아직 값을 구하지 않은 a -> b 로 가는 비용을 구할려고 한다면 a -> k -> b로 가는 비용을 보면 된다.
(a -> k + k-> b)가 더 비용이 적으면 갱신. 아니면 패스하는 식으로 구하면 되지 않을까?

이 코드를 추가했더니 아래와 같은 결과가 나왔다.

최댓값을 int max value로 설정해서 최댓값 + 어떤수를 비교해서 그렇다.

입력값을 보고 적당히 큰 값으로 바꿔서 다시해야겠다.

비용이 100000 보다 작거나 같다고 해서 100000으로 설정하고 다시 돌려봤다.

 

일단 테스트 케이스는 통과.

 

k = 1, k = 2, k = 3, ...을 쭉 보면서 경유했을때의 비용이 더 가까우면 갱신을 하기때문에

만약 두번 갈아타야하는 경우에도 (ex. a->b->c->d)

반복문에서 a->b, a->c, a->d, a->e를 쭉 보고 b->a, b->c, b->d, b->e 이런식으로 모든 경로의 최솟값을 확인하기 때문에

잘 구해지는 것 같다.

 

어떤 도시가 다른 모든 곳과 연결이 안되어있어서 못가는 경우에는 0을 출력하라고 되어있다.

위의 처리를 해주고 채점 결과를 돌렸더니

탈락

 

.....? 이번엔 문제도 잘 읽었고 잘 푼 것 같은데...뭐가 문제..?
모르겠어서 다른 사람들 풀이도 봤는데 똑같은것 같은데 뭐가 문제일까 생각을 해봤는데

INF값이 충분지 크지 않다는 것을 알게 되었다.

 

문제는 잘 읽었는데, 생각을 대충해서 틀렸다...

읽기만 하면 뭐해 계산을 해서 타당한 값을 설정을 했어야지

 

최단 경로 비용이

최대 100,000까지 들어올 수 있고

도시의 개수가 최대 100개 이므로 최대 99개의 간선을 이용해서 갈아타야할수도 있다.

이 경우 최소 비용은 100,000 * 99 인데 대충 100,000값을 집어넣고 충분히 큰 수라고 했으니 갱신이 잘못돼서 당연히 답이 안나왔던 것.

 

 

 

질문 게시판을 보니 다른 사람들은 못가는 곳을 0으로 처리 안해서 틀렸다고 하는데 나는 그 부분 처리도 해줬는데 답이 안나와서 

매우 당황했다...

이런데에서 실수하지 말자!!

---

풀이 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class G_11404 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());    // 도시의 개수
        int M = Integer.parseInt(br.readLine());    // 버스의 개수
        int INF = 10000001;

        int[][] dist = new int[N][N];
        for (int i = 0; i < N; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0; // 자기 자신으로 가는 비용은 0
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken());

            dist[a][b] = Math.min(dist[a][b], c);
        }

        for (int k = 0; k < N; k++) {
            for (int a = 0; a < N; a++) {
                for (int b = 0; b < N; b++) {
                    dist[a][b] = Math.min(dist[a][b], dist[a][k] + dist[k][b]);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (dist[i][j] == INF) {
                    sb.append("0").append(" ");
                } else {
                    sb.append(dist[i][j]).append(" ");
                }
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}