[PS] 백준 1507: 궁금한 민호

풀이 과정 🔎

• 가장 가까운 경우부터 체크하면서 도로를 추가해야 하는지, 다른 도로로 최소 이동 시간을 달성 가능한지 확인하면 어떨까 (주어진 게 최소 이동 시간이라고 해서 이런 생각이 들었던 듯)

• 이때, 확인되는 이동 시간에 따라 도로를 추가할지 결정하자.

  • 주어진 최소 이동 시간보다 작다면? 이미 갱신된 최솟값이 늘어날 수는 없음. 성립 불가능
  • 주어진 최소 이동 시간과 같다면? 지금까지 추가한 도로만으로 조건 만족됨. 추가 처리 불필요
  • 주어진 최소 이동 시간보다 크다면? 처음에는 이때 경우의 수가 다양해지지 않을까 고민했는데, 이미 추가한 도로를 경로에 포함시키고 새로운 도로를 추가한다면 그 도로가 연결하는 두 도시는 최소 이동 시간이 갱신되어 버리기 때문에 불가능하다는 생각이 들었다. 이 경우에는 무조건 최소 이동 시간을 비용으로 가지는 하나의 도로를 추가하면 된다고 결론내렸다.

• 그렇다면 현재까지 추가한 도로를 통해 모든 도시에서 모든 도시 사이의 최소 이동 시간을 가지고 있어야 한다.

• 플로이드-워셜로 도로를 추가할 때마다 새 도로를 경유해서 갱신할 수 있는 최소 이동 시간을 갱신하면 되겠다!

• 로직은 다음과 같이 정리했다.

  최소 이동 시간이 짧은 순으로 두 도시 x, y 사이의 이동 시간을 확인
  (1) 현재 이동 시간 < 주어진 최소 이동 시간이라면 불가능한 것으로 플래그 표시하고 종료
  (2) 현재 이동 시간 > 주어진 최소 이동 시간이라면 x, y 사이에 도로를 추가
  (2)-1. 서로 다른 모든 a, b 쌍에 대해 x, y 사이의 도로를 경유해서 이동하는 시간을 체크한 후 최솟값 갱신

정답 코드 ✅

// C++ 사용

#include <iostream>
#include <queue>
#define INF 50000
#define pnt pair<int, int>
#define ppnt pair<int, pnt>
using namespace std;

// 도시 간의 거리가 가까운 순서대로 체크
// 풀고 난 뒤 생각해 보니 우선순위 큐까지 쓸 필요 없이 벡터나 배열에 입력받아서 정렬하고 써도 됐겠다는 생각이 들었다.
priority_queue <ppnt, vector<ppnt>, greater<ppnt> > pq;
int map[20][20] = {0, }, dist[20][20] = {0, };

int main() {
  int n;
  cin>>n;
  
  // 주어진 거리 입력 & 탐색된 거리 초기화
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      cin>>map[i][j];
      if(i != j) {
        dist[i][j] = INF;
      }
      if(j > i) {
        pq.push(make_pair(map[i][j], make_pair(i, j)));
      }
    }
  }

  bool isAble = true;
  int sum = 0, distance, update, x, y;
  
  // 가까운 순으로 주어진 모든 거리 정보 체크
  while(!pq.empty() && isAble) {
    distance = pq.top().first;
    x = pq.top().second.first;
    y = pq.top().second.second;
    pq.pop();
   
    if(dist[x][y] < distance) {
      // 현재 두 도시 사이의 최소 거리가 주어진 거리보다 가까운 경우: 성립 불가능
      isAble = false;
    } else if(dist[x][y] > distance) {
      // 현재 두 도시 사이의 최소 거리가 주어진 거리보다 먼 경우: 도로를 추가
      dist[x][y] = dist[y][x] = distance;
      sum += distance;
      
      // 해당 도로를 경유할 때의 최소 거리 갱신
      for(int start = 0; start < n; start++) {
        for(int end = start + 1; end < n; end++) {
          update = INF;
          if(dist[x][start] != INF && dist[y][end] != INF) {
            update = dist[x][start] + dist[y][end];
          }
          if(dist[x][end] != INF && dist[y][start] != INF && update > dist[x][end] + dist[y][start]) {
            update = dist[x][end] + dist[y][start];
          }

          if(update != INF && update + distance < dist[start][end]) {
            dist[start][end] = dist[end][start] = update + distance;
          }
        }
      }
    }
  } 

  if(isAble) {
    cout<<sum<<'\n';
  } else {
    cout<<"-1\n";
  }
  return 0;
}