[Algorithm]Baekjoon 10159번 :: 저울

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
 
using namespace std;
 
int n, m;
int graph[2][101][101] = { 0 };
const int maxNum = 0x3f3f3f3f;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    memset(graph, 0x3f, sizeof(graph));
 
    for (int i = 1; i <= n; ++i)
    {
        graph[0][i][i] = graph[1][i][i] = 0;
    }
 
    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;
 
        graph[0][a][b] = 1;
        graph[1][b][a] = 1;
    }
 
    for (int k = 1; k <= n; ++k)
    {
        for (int i = 1; i <= n; ++i)
        {
            if (graph[0][i][k] != 0x3f3f3f3f)
            {
                for (int j = 1; j <= n; ++j)
                {
                    graph[0][i][j] = min(graph[0][i][j], graph[0][i][k] + graph[0][k][j]);
                }
            }
 
            if (graph[1][i][k] != 0x3f3f3f3f)
            {
                for (int j = 1; j <= n; ++j)
                {
                    graph[1][i][j] = min(graph[1][i][j], graph[1][i][k] + graph[1][k][j]);
                }
            }
        }
    }
 
    vector<int> results;
 
    for (int i = 1; i <= n; ++i)
    {
        int count = 0;
 
        for (int j = 1; j <= n; ++j)
        {
            if (i == j) continue;
 
            if (graph[0][i][j] != maxNum ||
                graph[1][i][j] != maxNum)
            {
                ++count;
            }
        }
 
        results.push_back(n - count - 1);
    }
    
    for (int i = 0; i < results.size(); ++i)
    {
        printf("%d\n", results[i]);
    }
}
 
 

 

각 노드끼리의 상관관계를 파악할수있느냐를 묻는 문제이다.

무게를 비교하기위해서 그래프형태를 이룰 때, 한가지 방향으로만 이루어져야 한다.

즉, 숫자 a,b가 주어지면 앞에있는숫자는 뒤에있는 숫자보다 무겁다... 로만 그래프를 만든게 있어야하고

뒤에있는 숫자는 앞에있는 숫자보다 가볍다.. 로만 만든 그래프가 있어야 한다.

 

두 그래프로 플로이드와샬을 진행하면 각각의 방향에대해 최단거리를 구할 수 있는데, 가벼운쪽이든 무거운쪽이든 maxNum값이 아니라면(유효한 거리라면) 비교를 할 수 있다는 것이기 때문에 카운팅해주면 된다.

출력해야하는 답 자체는 비교할 수 없는 개수를 구하는 거니 n - 1(자기자신) - 카운팅개수.. 를 출력해주면 된다.