#1608 스타대회

이 문제를 그래프로 해석해서 풀어보자.

각 학생은 다음 두 집합중에 하나에 속하게 된다.

A = {우승가능성이 있는 학생}

B = {어떻게 해도 항상 패배하는 학생}

 

우리의 목표는 A에 속한 학생들을 모두 구하는 것이 목적이다.

천적관계에 대해서 간선을 만든다고 생각해보자.

즉 x가 항상  y를 이긴다면 x->y인 모든 간선을 추가한다고 생각해보자.

첫번째 아이디어는 다음과 같다.

A에 속해있는 임의의 정점을 a, B에 속해있는 임의의 정점을 b라고 해보자.

 

우선 연결그래프가 아닐 경우는 무조건 모든 정점이 되므로 넘어가자. (이건 쉬우니 생략하겠다...)

 

1. b에서 a로 가는 간선은 존재할 수 없다.

 

쉬운 증명: a는 이길 가능성이 있는데, a를 b가 이긴다는 것은 b도 이길 가능성이 있다는 뜻. 직관적으로 쉽게 생각 가능하나, 엄밀한 부분에서 디테일이 아쉽다. 실제 풀이를 짤 때는 위의 생각 정도로 풀이를 구현했으나, 아래는 조금 더 엄밀하게 생각해 본 것이다.

 

어려운 증명:  정점 x가 우승가능하다라는 생각은 x에서 시작해서 모든 정점에 간선을 타고 도달 가능하다는 의미이다.

따라서 y->x가 존재한다면 y에서 시작해서 그 간선을 타고 바로 x로 이동하면, x에서 도착하고, 따라서 모든 정점에 이동 가능하다.

 

2.같은 SCC에 속한 정점들은 속해 있는 집합이 동일하다.

1에 기반한 것인데, 같은 SCC에 속해 있는 두 정점 x,y는 x에서 y로 도착하는 경로가 존재하고, y에서 x로 가는 겨올가 존재한다는 뜻이다. 만약 x,y가 서로 반대 집합에 속해 있다면, 둘 중 하나는 A, 하나는 B에 속해야 하는데, B->A로 가는 간선은 존재 할 수 없으므로, 이는 모순이 된다.

 

우리는 2번 생각까지 하고 SCC로 묶어내자 라는 생각을 해볼 수 있다.

SCC로 묶게된다면, 그래프는 DAG로 바뀐다. 

 

3.A집합의 크기는 1이상이다. 따라서 SCC에서 indegree가 0인 정점은 항상 A에 속한다.

우선 A집합의 크기는 1이상인 것은 자명하니 넘어가자.

이제 indegree 0인 것에 대해 증명해보자.

편의상 indegree가 0인 것이 1개라고 가정하자.  

귀류법으로 증명하자.

만약, 그 정점이 B였다면, 그 정점으로부터 나머지 모든 정점이 간선을 타고 이어지기 때문에, 1번에 의해서

모든 정점이 B에 속하게 된다. 그렇다면, A집합의 크기가 0이게 되므로 모순이다.

 

따라서 그 정점은 A였을 수 밖에 없다.

 

indegree가 0인 것이 여러개라면 어떨까?

이는 아래 4번을 먼저 보고 와서 해결해보자.

4번은 천적관계가 아닌 두 정점에 관해서 생각해보자.

 

4.모든 A집합의 원소들은 B집합과 천적관계이다. 

즉 다시말하면, 천적관계가 아닌 두 선수는 같은 집합에 속한다.

 

B집합의 원소 b에 대해서 천적이 아닌 A집합의 원소 a가 존재한다고 가정해보자.

그렇다면 b가 a를 이길수도 있었다는 뜻이고 이는 전제에 모순이다.

 

이를 이용하면 3번의 마지막 내용을 쉽게 증명할 수 있다.

indegree가 0인 정점들 끼리는 edge가 없기 때문에 천적이 아니다.

따라서 모두 A이거나 모두 B인데, 모두 B인 경우는 3번에서 증명했던 것처럼 모순이므로 모두 A이다.

 

5. 최종 풀이

scc로 묶고 queue에 indegree 0인 정점들을 전부 넣는다.

그리고, queue의 원소를 pop하면서 그 원소와 천적관계가 아니었던 정점이 있다면 전부 넣는다.

이를 반복해주면 된다.

조심해주어야 할 것은 queue의 원소는 scc의 원소인데 천적관계는 scc가 아니라 원래 그래프에서를 기준으로 해 주어야 한다.

또한 시간복잡도도 조심해야 한다.

나는 pq로 다익스트라 처럼 짰다.

 

사실 이 문제만 처음 봤을 때는 발상이 힘들었다.

풀지는 못한 문제지만, 

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

위 문제를 고민하며 했던 생각들이 도움이 됐던 것 같다.