[ BOJ 백준 10159번 - 저울 ] 해설 및 코드

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

 

목적

물건 쌍의 비교 결과를 알 수 있는지 구하자.

 

접근법

1. 플로이드 와샬 알고리즘을 이용하여 방향 그래프의 연결 여부를 구한다.

2. 비교 결과를 알 수 있는지 여부는 양방향으로 검사한다.

 

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

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

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