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

🔗 문제

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

 

 

✏️ 풀이

• N개의 정점 (N ≤ 100)
• M번의 대소 비교

처음에는 대소 관계 위상정렬인가 싶었다.

하지만 문제는 i번째 아이템이 다른 아이템의 순서를 파악하지 못 하는 수를 출력해줘야 한다.

 

대소 관계가 주어졌다는 건 그래프 관계로 만들 수 있다는 것이고, 순서를 파악하지 못 한다는건 분리된 그래프라는거 아닐까? 라는 생각으로 dfs랑 플로이드워셜 알고리즘을 생각했다.

 

dfs는 내가 잘 못 하니까 플로이드 워셜 알고리즘으로 풀었다 🙂

 

플로이드 워셜 문제는 주로 정점이 500개 이하일때 권장되는 풀이이므로 바로 적용해서 풀었다.

 

플로이드 워셜 시간복잡도 : O(V^3)
모든 정점 쌍에 대한 최단 경로를 계산하느라 3중 포문을 돌기 때문임

 

💾  소스

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAX_N = 100+1;
int adj[MAX_N][MAX_N] = {false, };

int main() 
{
    int N, M, A, B;
    cin >> N >> M;
    
    for(int k=1; k<=N; ++k)
        for(int i=1; i<=N; ++i)
            adj[k][i] = 1e9;

    for(int i=0; i<M; ++i)
    {
        cin >> A >> B;
        adj[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(adj[i][k] == 1e9 || adj[k][j] == 1e9) continue;
                if(adj[i][k] + adj[k][j] < adj[i][j])
                    adj[i][j] = adj[i][k] + adj[k][j];
            }
        }
    }

    for(int i=1; i<=N; ++i)
    {
        int cnt = 0;
        for(int j=1; j<=N; ++j)
        {
            if (i == j) continue;
            if (adj[i][j] == 1e9 && adj[j][i] == 1e9) cnt++;
        }
        cout << cnt << "\\n";
    }
        
    return 0;
}