[백준] No.3648 - 아이돌 (C++, 2-SAT)

문제

 

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

3648번: 아이돌

 

 

풀이

 

solved.ac 난이도: Platium 4

 

 

2-SAT 문제에 대하여 모른다면 반드시 먼저 공부하고 오자.

[2-SAT] 2 - Satisfiability Problem / 충족 가능성 문제 (알고스팟 회의실 배정 풀이)

 

이번 문제도 심사위원의 투표 A와 B중 하나는 반드시 영향이 있어야 하기 때문에 두 가지 변수로 절을 생성할 수 있는 2-SAT 문제이다.

각 절은 (A || B) 로 표현된다.

 

심사위원들의 투표를 토대로 함의 그래프를 생성해주면 되지만 추가적으로 첫 번째 참가자인 상근이가 다음 라운드에 진출해야 한다.

따라서 다음의 그래프도 추가해준다.

!A: 상근이가 반대투표를 받은 경우

A: 상근이가 찬성 투표를 받은 경우

 

상근이가 다음 라운드로 진출하기 위해서는 A가 true이어야 하고, !A는 false이어야 한다.

2-SAT 게시글에서 설명했듯이 2-SAT 를 풀 때 방문되지 않은 정점은 false로 먼저 설정해야 손해가 없다.

따라서 !A는 A보다 먼저 방문되어야 상근이가 다음 라운드로 진출할 수 있다.

 

타잔 SCC에서는 DFS 스패닝 트리의 역순으로, 즉 하위의 SCC가 먼저 결정되므로 하위의 SCC가 더 작은 scc_label(생성된 순서) 값을 갖는다.

따라서 !A의 index값은 3이고 A의 index값은 2이기 때문에 (모든 투표의 A와 !A의 값을 일렬로 표현했음)

 

scc_label[2]>scc_label[3]인 경우는 A가 먼저 방문되어 false로 설정되는 경우이다.

해당 경우는 상근이가 다음 라운드에 진출할 수 없다.

 

추가적으로 모든 투표(A)들에 대하여 

A와 !A가 같은 SCC에 속해있다면 두 값이 같은 boolean 값을 가져 2-SAT 문제를 해결할 수 없다.

 

코드