[백준] No.3648 - 아이돌 (C++, 2-SAT)
문제
https://www.acmicpc.net/problem/3648
3648번: 아이돌
각 테스트 케이스에 대해서, 상근이를 포함해, 다음 라운드 진출 목록을 심사위원의 의심 없이 만들 수 있으면 'yes'를, 없으면 'no'를 출력한다.
www.acmicpc.net
풀이
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 문제를 해결할 수 없다.
코드
| #include<stdio.h> | |
| #include<vector> | |
| #include<stack> | |
| #include<algorithm> | |
| using namespace std; | |
| int contestant_num, judges_num, node_num; | |
| vector<pair<int,int>> votes; | |
| vector<vector<int>> adj; | |
| vector<int> visited_order; | |
| vector<int> scc_label; | |
| stack<int> st; | |
| int order =1, scc_order =1; | |
| int FindSCC(int now_node){ | |
| int min_order = visited_order[now_node] = order++; | |
| st.push(now_node); | |
| int next_node; | |
| for(int i=0; i<adj[now_node].size() ; ++i){ | |
| next_node = adj[now_node][i]; | |
| if(visited_order[next_node] == -1) | |
| min_order = min(min_order, FindSCC(next_node)); | |
| else if(scc_label[next_node] == -1) | |
| min_order = min(min_order, visited_order[next_node]); | |
| } | |
| if(min_order == visited_order[now_node]){ | |
| int temp; | |
| while(1){ | |
| temp = st.top(); | |
| st.pop(); | |
| scc_label[temp] = scc_order; | |
| if(temp == now_node) break; | |
| } | |
| ++scc_order; | |
| } | |
| return min_order; | |
| } | |
| void TarjanSCC(){ | |
| visited_order = vector<int>(node_num, -1); | |
| scc_label = vector<int>(node_num, -1); | |
| order = scc_order = 1; | |
| for(int i=2; i<node_num ; ++i) | |
| if(visited_order[i] == -1) | |
| FindSCC(i); | |
| } | |
| bool Solve2SAT(){ | |
| TarjanSCC(); | |
| if(scc_label[2]>scc_label[3]) //타잔 SCC의 SCC order는 DFS 스패닝 그래프의 역순이므로 | |
| return false; | |
| for(int i=2; i<node_num ; i+=2){ | |
| if(scc_label[i] == scc_label[i+1]) | |
| return false; | |
| } | |
| return true; | |
| } | |
| int main(){ | |
| while(scanf("%d %d", &contestant_num, &judges_num) != EOF){ | |
| node_num = ((contestant_num*2) + 1)*2; | |
| adj = vector<vector<int>>(node_num); | |
| adj[3].push_back(2); //상근이가 반드시 뽑히도록 함의 그래프 간선을 추가 | |
| int a,b, not_a, not_b; | |
| for(int i=0; i<judges_num ; ++i){ | |
| scanf("%d %d",&a, &b); | |
| a*=2; not_a = a +1; | |
| b*=2; not_b = b +1; | |
| if(a<0){ | |
| a = -1*(a) +1; | |
| not_a = a -1; | |
| } | |
| if(b<0){ | |
| b = -1*(b) +1; | |
| not_b = b - 1; | |
| } | |
| adj[not_a].push_back(b); | |
| adj[not_b].push_back(a); | |
| } | |
| if(Solve2SAT()) | |
| printf("yes\n"); | |
| else | |
| printf("no\n"); | |
| } | |
| return 0; | |
| } |