백준 1507번 궁금한 민호 [플로이드] :: 마이구미

이번 글은 백준 알고리즘 문제 "궁금한 민호"를 다뤄본다.

플로이드 와샬 알고리즘을 통해 해결한다.

백준 알고리즘 1507번 궁금한 민호 - https://www.acmicpc.net/problem/1507

강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다.

도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다.

강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로가 몇 개 있는지를 구해보려고 한다.

예를 들어, 예제의 경우에 모든 도시 사이에 강호가 구한 값을 가지는 도로가 존재한다고 해도 된다. 하지만, 이 도로의 개수는 최솟값이 아니다. 예를 들어, 도시 1-2, 2-3, 1-4, 3-4, 4-5, 3-5를 연결하는 도로만 있다고 가정해도, 강호가 구한 모든 쌍의 최솟값을 구할 수 있다. 이 경우 도로의 개수는 6개이고, 모든 도로의 시간의 합은 55이다.

모든 쌍의 도시 사이의 최소 이동 시간이 주어졌을 때, 이 나라에 존재할 수 있는 도로의 개수의 최솟값과 그 때, 모든 도로의 시간의 합을 구하는 프로그램을 작성하시오.

문제는 각 도로에 대한 최단 경로에 대한 값이 주어진다.

이 값을 활용해서 최소 간선의 개수와 모든 간선에 대한 값의 합을 구하는 문제이다.

이 문제를 해결하기 위해서는 기본적으로 플로이드 와샬 알고리즘에 대한 이해가 필요하다.

알고 있지 않다면 본인이 작성한 플로이드 와샬 알고리즘 관련 글을 보고 오자.

플로이드 와샬 알고리즘은 최단 경로를 위해 사용한 알고리즘이다.

문제에서는 입력 예제는 도로 간의 최단 경로이다.

즉, 문제에서는 이미 최단 경로를 입력 예제로 주어진다.

우리는 최단 경로를 구하기 전 필요한 도시간의 간선들의 정보가 필요하다.

도시간의 간선들의 정보를 이용하여 최단 경로를 구할 수 있기 때문이다.

우리는 이렇게 생각해볼 수 있다.

문제에서는 사전에 플로이드 와샬 알고리즘을 통해 최단 경로를 구했다? 이렇게 가정하자.

그렇다면, 우리는 플로이드 와샬 알고리즘을 역으로 생각하여 문제를 해결할 수 있다.

1. 모든 도시를 간선으로 연결시킨다.

2. 거쳐가는 도시가 있을 경우 출발 도시와 도착 도시간의 간선은 없애버린다.

플로이드 와샬 알고리즘의 특성상 거쳐가는 모든 정점을 확인한다는 것을 알고 있다.

그렇다는 건, 출발 도시(i) -> 거쳐가는 도시(k) -> 도착 도시(j) 경로의 값이 존재한다면, 그것은 최단 경로이다.

그렇기에 i -> j의 간선은 없애버려도 된다.

// dist - 최단 경로, a - 간선 여부

if (dist[i][j] == dist[i][k] + dist[j][k]) {
a[i][j] = 0;
}

위 조건을 이용하여 플로이드 와샬 알고리즘을 역으로 활용하면, 초기 도시 간의 간선들의 정보를 구할 수 있다.

불가능한 경우는 거쳐가는 도시들의 합보다 최단 경로 클 경우를 조건으로 주면 된다.

최단 경로를 구해져있는데 거쳐가는 도시들의 경로의 합이 최단 경로보다 클 수는 없기 때문이다.

0 6 15 2 6
6 0 9 99 12
15 9 0 16 18
2 99 16 0 4
6 12 18 4 0

6 + 2 < 99

if (dist[i][j] > dist[i][k] + dist[k][j]) {
    System.out.println(-1);
    return;
}

역으로 활용하면 도시들의 간선들의 정보를 구할 수 있다.

이 양방향 그래프이기 때문에 방문 여부를 확인하여 도로의 합을 구할 수 있다.

자세한 건 아래의 Github을 통해 확인하길 바란다.

전체 소스 Github URL

https://github.com/hotehrud/acmicpc/blob/master/algorithm/Floyd/1507.java