[백준 / BOJ] C++ 11562 백양로 브레이크

11562번: 백양로 브레이크

 

문제

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

11562번: 백양로 브레이크

 

 

풀이

정점 간 양방향, 단방향 간선이 있을 때 출발지에서 목적지까지 경로가 이어지도록 하려면 몇 개의 단방향 간선을 양방향 간선으로 바꾸면 되는지 구하는 문제다. 즉, 최단 경로를 구하되 단방향 간선을 반대로 지나간 횟수를 구하면 된다.

 

간선은 시작점, 도착점, 방향의 정보를 입력받는다.

 

예시를 통해 알아보자 임의의 정점 a, b에 대해 a에서 b로 가는 최단 경로가 u->v 단방향 간선을 지난다고 하자. 이 경우엔 해당 간선을 양방향으로 바꿀 필요가 없다. 바꾸지 않아도 최단 경로의 일부이기 때문.

 

그럼 만약 u->v가 단방향 간선인데 최단 경로가 v->u를 지나야 한다고 해보자. 이 경우엔 단방향을 양방향으로 바꿔야 최단 경로의 일부가 된다.

 

u->v가 양방향 간선인 경우엔 이미 양방향이기 때문에 어느 방향으로 지나가더라도 바꿀 필요가 없다.

 

따라서 우리가 구해야할 것은 단방향 간선을 반대로 지나간 횟수이므로 단방향 간선 u->v가 입력된 경우 dist[u][v] = 0, dist[v][u] = 1로 해준다. 양방향 간선인 경우엔 둘 다 0으로 해준다.

 

이제 플로이드-워셜 알고리즘을 수행하면 dist[s][e]는 정점 s에서 정점 e로 가는 최단 경로에서 단방향 간선을 반대로 지나간 횟수가 될 것이다. 즉, 양방향으로 바꿔야 할 간선의 횟수다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, M, K, ans, dist[251][251];
  cin >> N >> M;
  // dist 배열 초기화
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
      dist[i][j] = i == j ? 0 : INF;
  // 간선 입력
  for (int i = 1; i <= M; i++) {
    int u, v, b;
    cin >> u >> v >> b;
    // 이 간선을 지나는 경로가 최단거리일 경우 양방향으로 바꿀 필요가 없다
    dist[u][v] = 0;
    // 양방향이면 dist[v][u]도 0
    dist[v][u] = b ? 0 : 1;
  }
  // 플로이드 워셜
  for (int k = 1; k <= N; k++)
    for (int i = 1; i <= N; i++)
      for (int j = 1; j <= N; j++)
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
  cin >> K;
  while (K--) {
    int s, e;
    cin >> s >> e;
    cout << dist[s][e] << '\n';
  }
  return 0;
}