[ BOJ 백준 11562번 - 백양로 브레이크 ] 해설 및 코드

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

목적

a에서 b로 가는데, 최소 몇 개의 일방통행인 길을 양방향 통행으로 바꿔야 하는지 구하자.

 

접근법

1. 다대다 경로 검색 문제로서, 플로이드 와샬 알고리즘을 적용한다.

2. 입력값에 따라 알고리즘에 사용될 배열 값을 0, 1, INF로 설정해준 뒤, 슥삭...

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
#define N 251
using namespace std;
 
int n, s[N][N];
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int m; cin >> n >> m;
    f(i, 1, n)f(j, 1, n) {
        if (i == j)s[i][j] = 0;
        else s[i][j] = N;
    }
 
    while (m--) {
        int a, b, c; cin >> a >> b >> c;
        s[a][b] = 0;
        if (c) s[b][a] = 0;
        else s[b][a] = 1;
    }
 
    f(k, 1, n)f(i, 1, n)f(j, 1, n) if (s[i][k] != N && s[k][j] != N) {
        int tmp = s[i][k] + s[k][j];
        if (s[i][j] > tmp)s[i][j] = tmp;
    }
 
    int k; cin >> k;
    while (k--) {
        int a, b; cin >> a >> b;
        cout << s[a][b] << '\n';
    }
 
    return 0;
}

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.