[백준] No.11280 - 2-SAT - 3 (C++, 2-SAT)

문제

 

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

11280번: 2-SAT - 3

 

 

풀이

 

solved.ac 난이도: Platium 4

 

 

일단 2-SAT에 대하여 공부하고 문제를 풀어봅시다.

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

 

이번 문제에서 위의 2-SAT 해설과 다른 점이 있다면 두가지 변수가 or로 연결된 절(clause)이 직접 주어지는 것입니다.

회의실 배정 문제와 다르게 직접 문제를 해석해 절을 형성하지 않아도 되므로

 

(A || B)에 대해서는 

 

• A가 진행되지 않으면 B가 진행되어야 합니다.
• B가 진행되지 않으면 A가 진행되어야 합니다.

 

이러한 표현을 'p이면 q이다'의 필요조건과 충족 조건 명제로 나타내면 다음과 같이 나타낼 수 있습니다.

 

• !A => B
• !B => A

따라서 다음과 같이 adj에 간선을 저장해 줍시다.

adj[not_a].push_back(b);

adj[not_b].push_back(a);

 

이번 문제는 식 f가 답을 가지는지만 확인하면 되기 때문에

함의 그래프로 표현한 후 같은 SCC에 대하여 라벨링을 해줍니다.

만약 같은 SCC안에 변수 A와 !A가 동시에 들어있다면

같은 SCC의 정점은 같은 boolean값을 가져야 하기 때문에 오답이 됩니다.

 

이외의 경우에는 f는 반드시 정답을 가집니다.

(물론 답은 여러 가지가 가능할 수 있습니다.)

 

f의 각 변수의 값을 구하는 문제도 풀어 봅시다.

 

 

 

코드