정화 코딩

https://www.acmicpc.net/problem/11281 2-SAT - 3 문제에 역추적만 추가된 문제이다. 2-SAT - 3 문제의 풀이는 이 글에서 확인할 수 있다. 이전 글에서 a or b 라는 절에 대해 ~a -> b 간선과 ~b -> a 간선을 만들어서 그래프를 구성하고, 그 그래프에서 SCC를 구해서 x와 ~x가 같은 컴포넌트에 속해 있는 경우가 없어야 한다는 것까지 알았다.이제 가능한 경우에 대해서, 각 변수를 어떻게 둬야 전체 식이 true가 되는 건지를 알고 싶은 것이다. 그래프를 구성하고 SCC를 구하는 것까지는 동일하다. SCC를 구한 다음에 scc 배열을 보면서 어떤 변수를 true로 설정해야 하는지만 결정해주면 된다. 우선 x 정점과 ~x 정점이 있을 때, 그 두 정점이..

https://www.acmicpc.net/problem/11280 2개의 변수가 or 연산으로 결합된 절 여러 개가 and 연산으로 결합된 식을 2-CNF 식이라고 한다.이러한 2-CNF 식이 true가 되도록 하는 문제를 2-SAT 문제라고 하고, 2-SAT 문제는 SCC를 통해서 해결할 수 있음이 알려져 있다. 그 이유는 다음과 같다. 전체 식이 true가 되려면 각 절은 모두 true가 되어야 한다.a or b 라는 절이 true가 되려면, a가 false면 b가 반드시 true여야 하고 b가 false면 a가 반드시 true여야 한다. 이제 어떤 정점이 참일 때 다른 어떤 정점도 연쇄적으로 참이 되어야 한다는 것을 그래프로 표현해보자.a or b 라는 절에 대해서는 그래프에 ~a -> b 간선과..