백준 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';
​​​​}
}