이 문제는, 주어진 두 지점에 대해서 '최소 몇번 역방향 다리를 새로 놓아야 접근할 수 있는지' 에 대해 묻는 문제이다.
뒤집어서 생각하는 것이 관건이다. 길이 없는 경우 거리를 무한대, 양방향 길이 있는 경우 거리를 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로 설정하면 해결하기 힘들 것이다.
'백준 > 카테고리별' 카테고리의 다른 글
[BOJ] 단계별로 풀어보기 - 우선순위 큐 (0) | 2020.07.06 |
---|---|
[BOJ] 2094 수학은 너무 쉬워 (0) | 2020.04.24 |
[BOJ] 11000 강의실 배정 (0) | 2020.04.17 |
[BOJ] 7579 앱 (0) | 2020.04.16 |
[BOJ] 2473 세 용액 (0) | 2020.04.11 |
댓글