(C++) - 백준(BOJ) 11562번 : 백양로 브레이크

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

11562번: 백양로 브레이크

플로이드 와샬 문제였습니다.

 

 

📕 풀이방법

📔 입력 및 초기화

  n,m,k 입력후 m만큼 u,v정점을 입력받은 것을 토대로 인접 그래프 adj를 형성해줍니다. 인접그래프의 초기값은 INF이며 갈 수 없는 경로는 1 갈 수 있다면 0으로 만들어줍니다. 

 

📔 풀이과정

 기존에 갈 수 있는 곳이라면 비용이 들지 않으나 인접해있지만 갈 수 없는 길을 가려면 길을 만들어줘야 하므로 1의 비용이 든다고 생각할 수 있습니다. 이 생각을 이용해 플로이드 와샬을 수행한다면 i -> j로 갈 때 필요한 비용 즉 만들어야 할 길의 수가 구해집니다. 이 때 자기 자신으로 가는 길에 대해서는 0으로 초기화를 해줘야합니다.

 

📔 정답출력

 k만큼 u,v를 입력받고 adj[u][v]를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f
using namespace std;
int n, m, k, adj[251][251];

int main(){
    fastio;
    memset(adj,INF,sizeof(adj));
    cin >> n >> m;

    for(int i = 0,u,v,b; i < m; i++){
        cin >> u >> v >> b;
        adj[u][v] = 0;
        if(!b) adj[v][u] = 1;
        if(b) adj[v][u] = 0;
    }

    for(int t = 1; t <= n; t++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(i == j) adj[i][j] = 0;
                adj[i][j] = min(adj[i][j], adj[i][t] + adj[t][j]);
            }
        }
    }

    cin >> k;

    for(int i = 0,u,v; i < k; i++){
        cin >> u >> v;
        cout << adj[u][v] << '\n';
    }
}