[C++][백준 10159] 저울

[문제]

10159번: 저울 (acmicpc.net)

10159번: 저울

---

[문제 풀이]

자기보다 가볍거나 무거운지를 알 수 없는 물건을 파악하면 된다.

플로이드 워셜을 이용해서 풀어보도록 하자!

 

나는 플로이드 워셜을 이용해서 자기로의 길이 뚫려있는지를 파악해보도록 하였다.

만일, 자기로의 길이 뚫려있다면 가벼운것을 자기로부터 길이 뚫려있다면 자기보다 무거운지를 파악 가능하니 해당 부분들을 모두 더해주고 전체 물건의 개수에서 자기자신(1)을 빼고 해당 부분들까지만 제거해주면 답이 나온다.

---

[코드]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int objects[2001][2001];
int n, m;

void floid(){

    for(int k = 1;k<=n;k++){
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=n;j++){
                if(objects[i][k] + objects[k][j] == 2){
                    objects[i][j] = 1;
                }
            }
        }
    }

    return;
}

int main(){
    cin>>n>>m;

    // fill(object[0],object[n+1],1);

    for(int i = 0;i<m;i++){
        int a, b;
        cin>>a>>b;
        objects[a][b] = 1;
    }

    floid();

    int count = 0;
    for(int i = 1;i<=n;i++){
        count = 0;
        for(int j = 1;j<=n;j++){
            if(objects[i][j] == 1 || objects[j][i] == 1){
                count++;
            }
        }
        cout<<n - count - 1<<endl;
    }

    return 0;
}