백준 20649. Stuck in a Rut

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

20649번: Stuck in a Rut

 

방향이 다른 모든 cow pair에 대해서, 다른 소의 간섭이 없을 때 두 개의 소가 충돌하는지, 충돌한다면 예상 충돌 시점은 언제인지를 구할 수 있을 것이다. (실제로는 다른 소의 간섭이 있기 때문에, 충돌 가능한 pair중 일부는 실제로 충돌하지 않는다는 점에 유의)

모든 가능한 충돌 정보를 vector에 넣어두고, 예상 충돌 시간이 작은 순서대로 순회하며 예상 충돌 중에서 실제로 일어난 충돌을 기록한다. 이 때 특정 시점에 충돌한 소는 그 시점 이후부터는 다른 소와 충돌할 수 없음을 고려하면, 예상 충돌 중 일어나지 않은 충돌을 제외할 수 있다.

실제로 일어난 충돌을 모두 알고 있다면 그 후부터는 간단한 dfs 문제가 된다.

(여담. 처음에 N, E, W, S 네 방향 모두 있는 줄 알고 엄청 고생하면서 구현했다. ㅠㅠ)

코드: https://www.acmicpc.net/source/36249611

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define int long long
struct cow {
    char dir;
    int x, y, i;
    void read() { cin >> dir >> x >> y; }
};
struct comp {
    int stopped, stopper, t, anotherT;
};
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<cow> north, east;
    for(int i = 0; i < n; i++) {
        cow c;
        c.i = i;
        c.read();
        if(c.dir == 'N')
            north.push_back(c);
        else
            east.push_back(c);
    }

    vector<comp> comps;
    for(auto& cow_n: north) {
        for(auto& cow_e: east) {
            int t1 = cow_e.y - cow_n.y;  // n충돌
            int t2 = cow_n.x - cow_e.x;  // e충돌
            if(t1 > 0 && t2 > 0) {
                if(t1 > t2) {
                    comps.push_back({cow_n.i, cow_e.i, t1, t2});
                } else if(t1 < t2) {
                    comps.push_back({cow_e.i, cow_n.i, t2, t1});
                }
            }
        }
    }
    
    sort(comps.begin(), comps.end(), [](comp a, comp b) { return a.t < b.t; });
    vector<int> stopped_time(n + 1);
    vector<vector<int>> edges(n + 1);
    for(auto& c: comps) {
        if((!stopped_time[c.stopper] || stopped_time[c.stopper] >= c.anotherT) && !stopped_time[c.stopped]) {
            stopped_time[c.stopped] = c.t;
            edges[c.stopper + 1].push_back(c.stopped + 1);
        }
    }
    function<int(int, int)> dfs = [&](int i, int p) {
        int ret = 1;
        for(auto& e: edges[i]) {
            if(e == p) continue;
            ret += dfs(e, i);
        }
        return ret;
    };

    for(int i = 1; i <= n; i++) {
        cout << dfs(i, -1) - 1 << '\n';
    }
}