[USACO] Stuck in a Rut (Silver)

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

 

한 소가 다른 소에 의해 풀을 먹지 못하는 관계를 트리로 생각한다면, 답은 각 노드에서 그 노드를 루트로 하는 트리의 노드 갯수에 1을 뺀 값이라는 걸 알 수 있다.

x, y좌표가 서로 다 다르므로 같은 방향이면서 같은 x, y 좌표인 경우를 배제할 수 있다.

그렇다면 같은 방향으로 가는 소들은 서로 영향을 미치지 않는다. 

그럼 서로 다른 방향으로 가는 소들을 생각해보면,

동쪽 방향으로 가는 소의 시작 좌표를 (x1, y1)이라고 하고, 북쪽 방향으로 가는 소의 시작 좌표를 (x2, y2)라고 하자.

그렇다면 x1<x2, y1>y2일때 서로 만나서 한 마리가 정지하거나 서로 갈 길 간다는 걸 알 수 있다.

그러나 소들의 위치에 따라 소들의 충돌 관계가 달라지므로, 동쪽 방향으로 가는 소들과 북쪽 방향으로 가는 소들을 각각 y, x좌표순으로 정렬하여 순서대로 봐주면서 먼저 충돌하면 연결하고 봐주는 과정에서 배제시켜서 트리를 완성하고 dfs로 답을 구해주면 된다.

 

코드 : https://github.com/djayy035/dj035_PS/tree/main