백준 10159번 - 저울

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

10159번: 저울

입력으로 주어지는 물건의 대소관계를 그래프로 표현하면 사이클이 없는 방향 그래프(DAG)로 표현할 수 있고 결과를 출력하기 위해 두 물건을 비교해야 하므로 위상정렬이 먼저 떠올랐습니다.

하지만 모든 물건들간에 비교가 필요하고 N의 최대가 100이라는 점에서 플로이드 와샬 알고리즘을 해결방법으로 생각해 낼 수 있었습니다.

 

 

• 필요한 배경지식

플로이드 와샬 알고리즘 : Floyd Warshall

 

 

 

• 문제 해결 방법

플로이드 와샬 알고리즘만 떠올릴 수 있다면 해결은 간단합니다.

물건사이의 대소 관계를 그래프로 표현하고 플로이드 와샬 알고리즘을 이용하여 물건 i,j사이의 경로가 있는지 없는지만 판단하면 문제를 해결할 수 있습니다.

물건 i와 j를 비교할때, i에서 j까지의 경로 또는 j에서 i까지의 경로 둘 중 하나만 존재하면 물건 i와 j의 비교 결과를 알 수 있으므로 그 결과를 출력해 주면 됩니다.

 

 

 

 

• C++ 전체 코드

#include<bits/stdc++.h>
using namespace std;

int N,M;
bool m[101][101]{};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>M;
    int a,b;
    for(int i=0; i<M; i++){
        cin>>a>>b;
        m[a][b] = true;
    }

    for(int k=1; k<=N; k++){
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                if(m[i][k] && m[k][j]) m[i][j] = true;
            }
        }
    }

    for(int i=1; i<=N; i++){
        int cnt = 0;
        for(int j=1; j<=N; j++){
            if(!m[i][j] && !m[j][i]) {
                if(i==j) continue;
                cnt++;
            }
        }
        cout<<cnt<<'\n';
    }
}