[BOJ] 11562 백양로 브레이크

이 문제는, 주어진 두 지점에 대해서 '최소 몇번 역방향 다리를 새로 놓아야 접근할 수 있는지' 에 대해 묻는 문제이다. 

뒤집어서 생각하는 것이 관건이다. 길이 없는 경우 거리를 무한대, 양방향 길이 있는 경우 거리를 0, 단방향만 있는 경우는 길이 없는 방향에 대해 1 값을 부여한다. 

그 후, Floyd-Warshall 알고리즘을 적용하면, 모든 Path에 대해 최단거리로 이동하기 위해 설치해야 할 다리의 갯수가 나온다. 

 

#include <cstdio>
#include <algorithm>

using namespace std;
const int INF = 1 << 29;

int Map[251][251];
int n, m, u, v, b, k, s, e;

int main(){
  scanf("%d %d", &n, &m);

  // 초기화
  for(int i = 0 ; i <= n ; i++){
    for(int j = 0 ; j <= n ; j++){
      Map[i][j] = INF;
      if(i==j) Map[i][j] = 0;
    }
  }
 
  // 반대방향 길이 없는 경우만 1 있으면 0
  for(int i = 0 ; i < m ; i++){
    scanf("%d %d %d", &u, &v, &b);
    if(b == 0 ){
      Map[u][v] = 0; 
      Map[v][u] = 1; 
    }
    else {
      Map[u][v] = 0; 
      Map[v][u] = 0; 
    }
  }

  // 정점간 반대 방향 거리를 구한다.
  for(int i = 1 ; i <= n ; i++){
    for(int j = 1 ; j <= n ; j++){
      for(int k = 1 ; k <= n ; k++){
        Map[j][k] = min(Map[j][k], Map[j][i] + Map[i][k]);
      }
    }
  }

  scanf("%d", &k);
  for(int i = 0 ; i < k ; i++){
    scanf("%d %d", &s, &e);
    printf("%d\n", Map[s][e]);
  }
  return 0;
}

이 문제는 아이디어가 중요한 것 같다. 단순히 연결되어 있으니 1로 설정하면 해결하기 힘들 것이다.