[백준 / BOJ] C++ 1507 궁금한 민호

1507번: 궁금한 민호

 

문제

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

1507번: 궁금한 민호

 

 

풀이

플로이드-워셜 알고리즘을 반대로 거슬러가면 된다. 플로이드-워셜은 i->j 시간보다 i->k , k->j 시간이 더 짧을 경우 i->j를 i->k , k->j로 갱신한다. 이 문제에선 이미 최단 시간이 구해져 있고 도로 개수를 최소화하는 것이 목적이다.

 

도로를 최소화하기 위해서 필요 없는 도로를 지워야한다. 예를 들면서 차례대로 살펴보자. i->j(직접 연결)로 가는 경우와 i->k , k->j(간접 연결)로 우회하는 경우를 비교해 보자.

 

1. 직접 연결인 경우보다 간접 연결인 경우가 더 작다면 -> 최단 경로가 아니므로 -1을 출력
2. 직접 연결인 경우와 간접 연결인 경우가 같다면 -> 간접 연결인 경우가 더 많은 도시를 아우르므로 직접 연결인 도로는 필요 X -> 직접 연결 도로 제거
3. 직접 연결인 경우보다 간접 연결인 경우보다 더 크다면 -> 필요한 경로라고 판단하고 넘어감

 

따라서 check라는 배열을 하나 만들어주고, 초기값은 1로 해준다. 위 조건 중 2번인 경우 직접 경로인 i->j, 즉 check[i][j] 값을 0으로 할당한다. 이후 check 배열 값이 1인 위치의 dist 값들을 모두 더해준다. (단, i->j 시간과 j->i 시간이 모두 더해진 값이기 때문에 2로 나누어 줘야 한다.)

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, ans = 0, dist[21][21], check[21][21];
  cin >> N;
  // dist 배열 입력 / check 모두 true
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++) {
      cin >> dist[i][j];
      check[i][j] = 1;
    }
  // 역플로이드 워셜
  for (int k = 1; k <= N; k++)
    for (int i = 1; i <= N; i++)
      for (int j = 1; j <= N; j++) {
      	// 자기 자신으로 향하는 경우 제외
        if (k == i || i == j || j == k)
          continue;
        if (dist[i][j] > dist[i][k] + dist[k][j]) { // 최단 경로가 아닌 경우
          cout << "-1\n";
          return 0;
        } else if (dist[i][j] == dist[i][k] + dist[k][j]) { // 직접 연결이 우회 연결과 같은 경우
          check[i][j] = 0;
        }
      }
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
      // 필요한 도로인 경우 시간 추가
      if (check[i][j])
        ans += dist[i][j];
  // i->j와 j->i 둘 다 포함되어 있으므로 2로 나눈다
  cout << ans / 2 << '\n';
  return 0;
}