백준 15752번 Hoofball [C++]

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

 

 

#문제 간단 정리

 

#문제 해결 방법

 

이 문제에서 중요한건

그래프 문제로 바꿔서 생각하는 것이다

 

일단 전달되는 것에서 그래프를 착안 할 수 있는데

전달되는걸 간선으로 처리한다고 하면

 

진입차수가 0인 소들은 농부가 직접 전해줄 수 밖에 없다

때문에 그래프 탐색으로 진입차수가 0인 소들의 진입들을 처리해주면

 

진입차수가 1 이상인 소들이 남아있을텐데

진입차수가 1인데 방문이 안됫다는 이유는 

서로 거리가 같아서 주고 받기 때문에

 

 

• 노드 A는 노드 B에게 공을 전달하고,
• 노드 B는 노드 A에게 공을 전달합니다.

와 같은 상황이 생기기 때문이다

 

즉 이렇게 진입차수가 1이상인 것들의 방문을 처리하면서 필요한 공 개수를 체크해 주면된다

 

 

결론적으로 그래프로 바꿔서 생각한 후에 진입차수에 대해서 생각해보면 된다

 

 

#전체 코드

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<pair<int, int>> cows(n); // {소의 위치, 소의 원래 인덱스}
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cows[i] = { x, i };
    }

    sort(cows.begin(), cows.end()); // 소의 위치를 기준으로 정렬

    vector<int> to(n);       // 각 소가 공을 전달할 소의 인덱스
    vector<int> indegree(n); // 각 소의 진입 차수

    for (int i = 0; i < n; i++) {
        int left_dist = INT_MAX;
        int right_dist = INT_MAX;

        if (i > 0) {
            left_dist = cows[i].first - cows[i - 1].first;
        }
        if (i < n - 1) {
            right_dist = cows[i + 1].first - cows[i].first;
        }

        if (left_dist <= right_dist) {
            // 왼쪽 소에게 전달
            to[i] = i - 1;
        }
        else {
            // 오른쪽 소에게 전달
            to[i] = i + 1;
        }

        // 공을 받는 소의 진입 차수 증가
        indegree[to[i]]++;
    }

    // 초기 공을 받아야 하는 소의 수 계산
    int balls = 0;
    vector<bool> visited(n, false);

    // 진입 차수가 0인 소들을 방문하여 도달할 수 있는 모든 소들을 방문 표시
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            balls++;
            int curr = i;
            while (!visited[curr]) {
                visited[curr] = true;
                curr = to[curr];
            }
        }
    }

    // 아직 방문하지 않은 소들을 탐색하여 사이클을 찾음
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            balls++; // 사이클마다 공 하나 추가
            int curr = i;
            while (!visited[curr]) {
                visited[curr] = true;
                curr = to[curr];
            }
        }
    }

    cout << balls << endl;

    return 0;
}