[C++][백준 2617] 구슬 찾기

[문제]

2617번: 구슬 찾기 (acmicpc.net)

2617번: 구슬 찾기

---

[문제 풀이]

우리들은 구슬이 가운데에 위치하지 못하는 구슬을 찾아야 하니 해당 구슬보다 가벼운 구슬의 크기가 절반보다 크거나 혹은 해당 구슬보다 무거운 구슬의 크기가 절반보다 큰 경우를 파악하면 된다.

 

플로이드 워셜을 이용해서 무게의 순서를 모두 파악해보자.

그리고 자기로의 길이 뚫린(자기보다 가벼운) 구슬과 자기로부터 뚫린(자기보다 무거운) 구슬을 각각 파악해보면 답이 나온다.

*여기선 자기로의 길일 뚫린을 자기보다 가벼운으로 설정했지만 무겹고와 가볍고 2개는 코드에 따라서 언제든지 바뀔 수 있다. 

---

[코드]

#include <iostream>
#include <algorithm>

using namespace std;

int n,m;
int scale[100][100];

void floid(){

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

    return;
}

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

    floid();

    int count = 0;
    int count_2 = 0;
    int answer = 0;
    int weight = 0;
    weight = (n+1) / 2;
    for(int i = 1;i<=n;i++){
        count = 0;
        count_2 = 0;
        for(int j = 1;j<=n;j++){
            if(j == i){ //자기 자신은 제외
                continue;
            }
            if(scale[i][j] == 1){ //자기보다 크고 작은지를 알기 위해서 2개의 조건으로 나누었다.
                count++;
            }
            if(scale[j][i] == 1){
                count_2++;
            }
        }
        if(count >= weight or count_2 >= weight){
            answer++;
        }
    }
    cout<<answer<<endl;
    return 0;
}