[C/C++] 백준 - 2617번 : 구슬 찾기

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

2617번: 구슬 찾기

문제

모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 아래와 같은 일을 하려 한다.

우리에게 주어진 것은 양팔 저울이다. 한 쌍의 구슬을 골라서 양팔 저울의 양쪽에 하나씩 올려 보면 어느 쪽이 무거운가를 알 수 있다. 이렇게 M개의 쌍을 골라서 각각 양팔 저울에 올려서 어느 것이 무거운가를 모두 알아냈다. 이 결과를 이용하여 무게가 중간이 될 가능성이 전혀 없는 구슬들은 먼저 제외한다.

예를 들어, N=5이고, M=4 쌍의 구슬에 대해서 어느 쪽이 무거운가를 알아낸 결과가 아래에 있다.

1. 구슬 2번이 구슬 1번보다 무겁다.
2. 구슬 4번이 구슬 3번보다 무겁다.
3. 구슬 5번이 구슬 1번보다 무겁다.
4. 구슬 4번이 구슬 2번보다 무겁다.

위와 같이 네 개의 결과만을 알고 있으면, 무게가 중간인 구슬을 정확하게 찾을 수는 없지만, 1번 구슬과 4번 구슬은 무게가 중간인 구슬이 절대 될 수 없다는 것은 확실히 알 수 있다. 1번 구슬보다 무거운 것이 2, 4, 5번 구슬이고, 4번 보다 가벼운 것이 1, 2, 3번이다. 따라서 답은 2개이다.

M 개의 쌍에 대한 결과를 보고 무게가 중간인 구슬이 될 수 없는 구슬의 개수를 구하는 프로그램을 작성하시오.

---

시험 끝나고 오랜만에 백준 문제 풀려고 하니 어렵더라구요. 골드4의 그래프 문제인데도 한참 걸려 해결하였습니다.

홀수 개의 구슬이 존재하고, M개의 쌍으로 2개의 구슬이 주어지면(a, b) a번 구슬이 b번 구슬보다 무겁다는 정보가 주어집니다.

우리는 위 정보들을 바탕으로 무게가 중간인 구슬이 될 수 없는 구슬의 개수를 구하면 됩니다.

 

홀수 개의 구슬 중에 무게가 중간인 구슬이 되려면 독립적인 구슬 각각과 비교하였을 때 현재의 구슬보다 더 무겁거나 가벼운 구슬의 개수가 N/2보다 많으면 안됩니다. N/2보다 많은 경우에는 이미 가운데 자리를 차지할 수 없다는 것을 의미합니다.

 

그럼 이제 어떻게 무겁거나 가벼운 구슬의 개수를 세어야하는지만 알아내면 되는데, 결국 이 문제에서 주어진 정보들을 나열해보면 그래프 형태가 됩니다. 어떻게 그래프 형태로 표현할 수 있냐?

 

a번 구슬이 b번 구슬보다 무겁다. (a > b)

b번 구슬이 c번 구슬보다 무겁다. (b > c)

c번 구슬이 d번 구슬보다 무겁다. (c > d)

 

위처럼 정보가 주어지면 우리는 a,b,c,d 각각 구슬의 무게를 정확히 알지는 못해도 a번 구슬이 c번 구슬과 d번 구슬보다 무겁다는 것을 알 수 있습니다. b라는 구슬이 c구슬보다 무겁고 c라는 구슬이 d구슬보다 무겁다는 것을 이미 알고 있기 때문입니다.

 

위처럼 말로 풀어 쓴 것을 그래프 형태로 나타내면은 구슬을 노드로 표현하고 무게 관계를 방향성으로 나타낼 수 있습니다.

 

이제 주어진 정보를 그래프 형태로 나타내면 이 문제는 깊이 우선 탐색으로 해결이 가능합니다.

 

다시 위 정보로 예를 들어보면 a번 구슬보다 가벼운 구슬의 개수를 세기 위해서는 우선 직접적으로 주어진 b번 구슬 1개를 구할 수 있습니다.

그리고 b번 구슬보다 가벼운 구슬은 결국 a번 구슬보다 가볍다는 것을 간접적으로 알 수 있기 때문에 b번보다 가벼운 구슬의 개수를 모두 세어주면 됩니다. 이런식으로 쭉 쭉 이어나가면 결국 알고자 하는 정보를 모두 알 수 있습니다.

 

즉, 재귀함수(깊이 우선 탐색)으로 우리가 원하는 정보를 모두 얻을 수 있고, 개수의 결과를 이용하여 무게가 중간이 될 수 있는지 없는지 판단하여 답을 구하면 되는 문제입니다.

 

단, 깊이 우선 탐색을 이용하여 문제를 해결할 때 방문처리를 꼭 하여 중복검사하는 일은 없도록 해야합니다.

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'

using namespace std;

int N, M, totalLower, totalUpper;
bool visited[99 + 1];
vector<int> adj[99 + 1][2];
bool checked[99 + 1][99 + 1];

void input(){
    cin >> N >> M;
    for(int i=0;i<M;i++){
        int upper, lower;
        cin >> upper >> lower;
        
        if(!checked[upper][lower]){
            checked[upper][lower] = true;
            adj[upper][0].push_back(lower);
        }
        if(!checked[lower][upper]){
            checked[lower][upper] = true;
            adj[lower][1].push_back(upper);
        } 
    }
}

void findAllLowerWeight(int index){
    if(adj[index][0].size() == 0) return;
    
    visited[index] = true;
    for(auto &t : adj[index][0]){
        if(!visited[t]){
            totalLower++;
            visited[t] = true;
            findAllLowerWeight(t);
        }
    }
}

void findAllUpperWeight(int index){
    if(adj[index][1].size() == 0) return;
    
    visited[index] = true;
    for(auto &t : adj[index][1]){
        if(!visited[t]){
            totalUpper++;
            visited[t] = true;
            findAllUpperWeight(t);
        }
    }
}

int solution(){
    int answer = 0;
    for(int i=1;i<=N;i++){
        totalLower = totalUpper = 0;

        memset(visited, false, sizeof(visited));
        findAllLowerWeight(i);

        memset(visited, false, sizeof(visited));
        findAllUpperWeight(i);

        if(totalLower > ((int)(N/2)) || totalUpper > ((int)(N/2))) {
            answer++;
        }
    }
    return answer;
}

int main(){
    fastio;
    input();
    cout << solution() << endl;

    return 0;
}