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

 

 

 

알고리즘 종류

    - 플로이드 와샬

 

 

 

사고 과정

    - 정점들 간에 비교를 나타내는 문제이다. A가 B보다 무겁고, B가 C보다 무거우면 A가 C보다 무거운 관계를 나타낼 수 있어야 한다. 관계의 표현이 '무겁다', '강하다', '빠르다' 등으로 표현 가능한 것을 다른 문제들에서 봤다. 각 정점들이 모든 다른 정점들과 비교를 할 수 있는 알고리즘이 필요하다.

    - 플로이드 와샬을 사용할 수 있을 것 같다. 플로이드 와샬은 선택한 정점을 거쳐서 목적지로 가는 알고리즘이다. 거쳐 가면서 무거운지 비교하면 쉽게 풀 수 있을 것 같다.

 

 

 

구현(C++)

#include <iostream>
#include <stdio.h>
 
using namespace std;
 
int n, m;
int mat[101][101];
 
 
void FW(){
    
    // k는 거쳐가는 정점, i는 출발 정점, j는 도착 정점
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                // 거쳐갈 때, 부호가 같다면 비교가 가능하다. 0일 때는 제외한다.
                // 예를 들어, A가 B보다 무겁고, B가 C보다 무거우면, A는 C보다 무겁다.
                // 만약, A가 B보다 무거운데, B가 C보다 가벼우면, A와 C의 관계는 모른다.
                if(mat[i][k] == mat[k][j] && mat[i][k] != 0){
                    mat[i][j] = mat[i][k];
                }
            }
        }
    }
}
 
int main(void){
    
    cin >> n >> m;
    
    int a, b;
    for(int i=0; i<m; i++){
        cin >> a >> b;
        // A가 B보다 무거우면, 반대로 B가 A보다 가볍다.
        mat[a][b] = -1;
        mat[b][a] = +1;
    }
    
    FW();
    
    // 출력
    for(int i=1; i<=n; i++){
        int cnt = 0;
        for(int j=1; j<=n; j++){
            if(mat[i][j] == 0){
                cnt ++;
            }
        }
        cout << cnt -1 << endl;
    }
}

 

 

 

시행착오