https://www.acmicpc.net/problem/1507
1507번: 궁금한 민호
강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다. 도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다. 강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로
www.acmicpc.net
플로이드를 잘 이해하고 있다면 쉽게 풀 수있는 문제이고, 그렇지 않다면 다소 어려울 수 있는 문제입니다.
플로이드 알고리즘을 사용해서 어떤 map[N][N] 배열을 만들었다면 만들어짐 map 배열의 특징은
(s -> m -> e) = (s -> e)
의 특징을 띄게 됩니다.
때문에 완성된 map배열의 s->e 경로는 s -> m -> e 로 똑같은 결과가 나오기 떄문에
없어도 되는 경로라고 할 수 있습니다.
-1의 출력( 불가능한 경우 )는 민호가 map 배열을 잘못 만들었을 경우가 해당합니다.
전체코드
#include <iostream> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #include <string> using namespace std; #define MAX_N 21 #define INF 1e9 int dp[MAX_N][MAX_N]; int dp2[MAX_N][MAX_N]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int N; cin >> N; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { int data; cin >> data; dp[i][j] = data; // 민호가 만든 최솟값 dp2[i][j] = data; // 민호가 만든 최솟값으로 만들 수 있는 최솟값 } } for (int m = 0; m < N; m++) { for (int s = 0; s < N; s++) { for (int e = 0; e < N; e++) { if (s == m || e == m) continue; // s -> m -> e 인경우에 m는 s와 e와 달라야 유효한 비교가 된다. if (dp[s][e] == dp[s][m] + dp[m][e]) { // 중간 지점을 거쳐갔을때와 바로 갔을 때 같다면 // 바로 가는 길을 없는길로 처리 해준다 dp2[s][e] = 0; } else if (dp[s][e] > dp[s][m] + dp[m][e]){ // 바로 가는길이 중간 지점을 거쳐오는 거보다 오래 걸리는 경우는 // 민호가 dp table을 잘못 만든 경우이다. cout << -1 << "\n"; return 0; } } } } int total = 0; // [i][j] = [j][i] 이므로 대각기준 오른쪽만 더해준다. for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { total += dp2[i][j]; } } cout << total << "\n"; }
'알고리즘 > [C++]BOJ' 카테고리의 다른 글
[백준BOJ] 11658 구간 합 구하기3 (0) | 2019.10.06 |
---|---|
[백준BOJ] 2660 회장뽑기 (0) | 2019.10.06 |
[백준BOJ] 9205 맥주 마시면서 걸어가기 (0) | 2019.10.06 |