Sat 문제 알고리즘 | Sat 문제 답을 믿으세요

당신은 주제를 찾고 있습니까 “sat 문제 알고리즘 – SAT 문제“? 다음 카테고리의 웹사이트 https://you.tfvp.org 에서 귀하의 모든 질문에 답변해 드립니다: https://you.tfvp.org/blog/. 바로 아래에서 답을 찾을 수 있습니다. 작성자 Olivier Bailleux 이(가) 작성한 기사에는 조회수 44,993회 및 좋아요 579개 개의 좋아요가 있습니다.

sat 문제 알고리즘 주제에 대한 동영상 보기

여기에서 이 주제에 대한 비디오를 시청하십시오. 주의 깊게 살펴보고 읽고 있는 내용에 대한 피드백을 제공하세요!

d여기에서 SAT 문제 – sat 문제 알고리즘 주제에 대한 세부정보를 참조하세요

This short video presents the problem of determining if a CNF propositional formula is consistent, namely, SAT.

sat 문제 알고리즘 주제에 대한 자세한 내용은 여기를 참조하세요.

2-SAT 문제(2-Satisfiability Problem) (수정: 2019-11-16)

변수의 개수가 적다면 이건 플로이드 알고리즘을 통해 확인할 수 있지만, 변수가 많다면? 네, 그렇습니다. 이 그래프를 SCC별로 분리한 후, 어떤 변수와 …

+ 여기에 자세히 보기

Source: m.blog.naver.com

Date Published: 4/25/2021

View: 9155

[그래프] 2-SAT문제 – 1 – JusticeHui가 PS하는 블로그

2-SAT문제란? 2-SAT(2-SATisfiability)문제는 충족 가능성 문제(satisfiability problem)의 한 종류입니다. 충족 가능성 문제란, 여러 개의 boolean …

+ 여기에 보기

Source: justicehui.github.io

Date Published: 11/23/2021

View: 2393

충족 가능성 문제 – 위키백과, 우리 모두의 백과사전

충족 가능성 문제(充足可能性問題, satisfiability problem, SAT)는 어떠한 변수들로 이루어진 논리식이 주어졌을 때, 그 논리식이 참이 되는 변수값이 존재하는지를 …

+ 여기에 표시

Source: ko.wikipedia.org

Date Published: 6/1/2022

View: 4994

2-SAT 및 그의 응용

아래는 2-SAT의 구현을 체크할 수 있는 BOJ의 11281번 2-SAT – 4 문제에 대한 필자의 코드다. #include #include #include  …

+ 여기에 자세히 보기

Source: www.secmem.org

Date Published: 3/2/2022

View: 1676

[알고리즘 문제 모음] 2-SAT (2 – Satisfiability Problem, 충족 …

[알고리즘 문제 모음] 2-SAT (2 – Satisfiability Problem, 충족 가능성 문제). EVEerNew 2021. 4. 14. 23:32. 반응형. *문제들의 난이도 분류는 종만북 혹은 …

+ 여기에 더 보기

Source: everenew.tistory.com

Date Published: 5/1/2022

View: 3936

16992번 – – 3-SAT 스페셜 저지전체 채점

문제. 3-SAT은 N개의 불리언 변수 …

+ 여기에 더 보기

Source: www.acmicpc.net

Date Published: 9/13/2021

View: 2463

2-SAT(2-CNF Satisfiability Problem) – Sevity – Tistory

먼저 절, 명제, 조건문 이 세가지가 헷갈리기 쉬운데, 이 알고리즘을 이해 … 2-SAT(2-SATisfiability)문제는 충족 가능성 문제(satisfiability …

+ 여기를 클릭

Source: sevity.tistory.com

Date Published: 12/21/2021

View: 7952

algospot.com :: 2-SAT – 알고스팟

2-SAT 문제는 O(n+m) linear time에 풀 수 있는 유명한 해법이 존재합니다. … 위의 조건을 검사하는 가장 (코딩이) 쉬운 방법은, floyd-warshall 알고리즘과 비슷한 …

+ 여기에 자세히 보기

Source: www.algospot.com

Date Published: 3/24/2021

View: 8151

Algorithm in A..Z – 2-SAT – 개발일지

* 충족 가능성 문제 : Boolean으로 이루어진 식이 있을 때 해당 식이 True인 경우를 찾는 문제 · (Conjunctive Normal Form)라고 한다. · 각 절의 변수의 …

+ 여기에 더 보기

Source: rkdxowhd98.tistory.com

Date Published: 3/8/2022

View: 8853

2-SAT (2-satisfiability) – algorithm

2-satisfiability 문제, ‘투셋’이라고 읽습니다. SCC 문서를 먼저 읽는 것을 추천합니다. 코드. 정리. 2-SAT 이란? SCC …

+ 여기에 보기

Source: hgkim.gitbooks.io

Date Published: 7/23/2021

View: 6596

주제와 관련된 이미지 sat 문제 알고리즘

주제와 관련된 더 많은 사진을 참조하십시오 SAT 문제. 댓글에서 더 많은 관련 이미지를 보거나 필요한 경우 더 많은 관련 기사를 볼 수 있습니다.

---

주제에 대한 기사 평가 sat 문제 알고리즘

• Author: Olivier Bailleux
• Views: 조회수 44,993회
• Likes: 좋아요 579개
• Date Published: 2018. 3. 16.
• Video Url link: https://www.youtube.com/watch?v=SAXGKCnOuP8

2-SAT 문제(2-Satisfiability Problem) (수정: 2019-11-16)

안녕하세요. 이번에 강의할 내용은 2-SAT(2-Satisfiability)이라는 좀 생소할 수 있는 내용입니다!

이건 충족 가능성 문제(satisfiability problem) 중 하나인데,

충족 가능성 문제는 여러 개의 boolean 변수들(true, false 중 하나의 값만 가질 수 있는)로 이루어진 boolean expression이 있을 때,

각 변수의 값을 true, false 중 하나로 설정하여 전체 식의 결과를 true로 만들 수 있느냐는 문제입니다.

▲ 사진 출처: 코드포스 튜토리얼 페이지

이번 글은 명제와 깊은 관련이 있기 때문에, 이산구조 중 명제에 대한 지식이 좀 필요합니다.

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

이 문제에서 SAT 문제가 무엇인지에 대해 대략 설명해주고 있는데요.

이러한 식 f가 있으면 x1 = x2 = false, x3 = true로 정하면 f가 true가 될 수 있지만,

(ㄱ자 모양 연산자는 NOT, 위로 뾰족한 연산자는 AND, 아래로 뾰족한 연산자는 OR입니다.)

이런 식의 경우 x1에 무슨 값을 넣어도 f가 true가 될 수 없습니다.

이렇게 f가 어떻게 주어지느냐에 따라서 f를 true로 만들 수도, 없을 수도 있습니다.

이때 식 f는 항상 괄호로 둘러싸여 있고 안쪽은 두 변수 혹은 NOT 변수들의 OR 연산으로만 이루어져 있으며, 바깥엔 AND 연산으로만 이루어져 있는 2중 구조를 띄고 있는데(NOT까지 포함하면 3중)

이때 괄호 단위의, OR 연산으로만 이루어진 부분을 절(clause)이라 하며, 이렇게 절의 AND 연산으로만 표현된 식의 형태를 CNF(Conjunctive Normal Form)라고 합니다.

각 절이 모두 true여야만 전체식도 true가 될 것이고, 따라서 각 절의 변수들 중 하나라도 true가 되도록 만드는 것이 문제를 푸는 방향입니다.

이때 각 절의 변수 개수가 최대 2개인 경우를 2-SAT이라고 칭합니다. 최대 k개는 k-SAT인 식.

3-SAT 이상의 식들은 모두 변형하여 3-SAT의 꼴로 나타낼 수 있으며, 3-SAT 문제를 푸는 것은 NP-Hard 문제이지만… 2-SAT 문제만은 다항 시간에 풀 수 있습니다.

도대체 왜 뜬금없이 이런 난해한 개념이 나오느냐?

왜냐면, 2-SAT 문제를 푸는 방법이 SCC를 응용한 것이기 때문입니다;; 어?

네. 아직 그래프 챕터는 안 끝났습니다. 게다가, 그래프에서 굉장히 중요한 파트도 아직 안 했고…

두 변수 p, q가 있을 때, p가 참이면 q도 참이라는 뜻의 명제를 p ⇒ q로 표현 가능한데요.

p → q는 단순히 원래부터 주어져 있던 명제이고, 중간에 r이라는 또다른 변수를 거쳐서

p → r, r → q가 성립하면 삼단논법에 의해서 간접적으로 p가 참이면 q도 참이 되고 이런 관계를 2중 화살표로 나타내서 p ⇒ q로 표현합니다. 이런 과정을 추론이라고도 합니다.

여기서, 처음부터 있던 명제들로 인해 어떤 변수 x에 대해 x ⇒ ¬x인 동시에 ¬x ⇒ x가 성립한다면, 이 명제들의 묶음에서는 모순이 발생한다고 할 수 있습니다. 한쪽 명제만 있다면야 좌변이 거짓이고 우변이 참이면 성립은 하는데, 양쪽 명제가 다 있다면… 이런 모순이 또 없죠.

그렇다면 처음부터 있던 명제들은 어떻게 고를까요? 이게 2-SAT 문제에서만 가능합니다.

2-SAT 문제에서 어떤 절 하나를 살펴봅시다. 각 절이 true여야 하니까, 절에 들어있는 두 항 중 적어도 하나는 참이어야 합니다.

(x1∨x2)라는 절이 있다면, 만약 x1이 거짓이라면 x2는 참이어야만 하고, x2가 거짓이면 반대로 x1이 참이어야 전체 식이 true가 될 가능성이 생깁니다. 아니면 둘 다 거짓이 되어 절대 전체 식이 true가 될 수가 없습니다.

(x1∨¬x2)라는 절이 있다면, x1이 거짓이면 ¬x2가 참이어야 하는데 이 말은 x2가 거짓이어야 한다는 의미이며, ¬x2가 거짓이면, 즉 x2가 참이면 x1이 참이어야 합니다.

이런 식으로 만약 두 항 중 하나가 거짓이라면 나머지 하나는 참이어야 한다는 명제들을 모두 모아보는 겁니다.

절 (x1∨x2)는 다음과 같은 2개의 명제로 나타낼 수 있습니다.

¬x1 → x2, ¬x2 → x1

절 (x1∨¬x2)는 다음과 같은 2개의 명제로 나타낼 수 있습니다.

¬x1 → ¬x2, ¬(¬x2) = x2 → x1

이런 식으로 모든 절에서 각각 두 개의 명제를 추출합니다. 예를 들어,

이 식에서는 이런 명제들을 끌어내야 합니다.

x1 → x2, ¬x2 → ¬x1, x2 → x3, ¬x3 → ¬x2, ¬x1 → x3, ¬x3 → x1, ¬x3 → x2, ¬x2 → x3

이제 각 변수와 NOT 변수를 하나의 정점이라 생각하고, 이런 → 관계들을 간선이라 생각한다면,

x1 → ¬x1과 ¬x1 → x1 꼴의, 자신의 NOT 형 변수로 가는 경로가 양쪽으로 존재하는 경우가 하나라도 존재한다면 전체 식을 참으로 만들 방법이 없는 게 확실합니다.

변수의 개수가 적다면 이건 플로이드 알고리즘을 통해 확인할 수 있지만, 변수가 많다면?

네, 그렇습니다. 이 그래프를 SCC별로 분리한 후, 어떤 변수와 NOT 형 변수가 같은 SCC에 있는 경우가 있는지를 체크하는 식으로 확인할 수가 있습니다!! 그렇다면 서로간에 경로가 존재한다는 의미니까요.

어떤 식 f가 저러할 때, 이걸 그래프 모델링하면 이렇게 됩니다.

SCC별로 분리하면 이렇게 되고,

보기 좋게 재배열하면 이렇게 됩니다.

indegree가 0인 SCC는 {x4}, {x1, x2, x3} 2개입니다.

이때, 항상 대칭형의 명제들만을 가지고 그래프를 만들었기 때문에 결과 그래프도 항상 대칭형이 됩니다.

여튼 여기서 주목해야 할 점은, p → q라는 명제가 있을 때 p가 거짓이면 q는 참이어도 거짓이어도 명제를 해치지 않지만, p가 참이면 q도 반드시 참이어야 합니다.

따라서 하나의 SCC 안에 있는 정점들은 그 중 하나라도 참이면 나머지도 모두 참이어야 하고,

따라서 SCC 안에 p와 ¬p가 동시에 존재한다면 둘 다 참일 수는 없으므로 모순이 됩니다.

그럼 일단 SCC 안에 p, ¬p가 동시에 존재하면 f 식을 참으로 만들 수 없는 건 알았는데요.

그럼 그런 경우가 하나도 없으면 f 식을 반드시 참으로 만들 수 있을까요? 그렇다고 합니다.

일단 그렇다고 믿고(?) “2-SAT 3” 문제를 풀어본다면 아래와 같습니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #include < cstdio > #include < cstring > #include < vector > #include < stack > #include < utility > #include < algorithm > using namespace std ; typedef pair < int , int > P; const int MAX = 10000 ; int N, M, cnt, scc, dfsn[MAX * 2 ], sn[MAX * 2 ]; vector < int > adj[MAX * 2 ]; bool finished[MAX * 2 ]; stack < int > S; // 자신의 not literal의 정점 번호 리턴 inline int oppo( int n){ return n% 2 ? n – 1 : n + 1 ; } // GetSCCsByDFS로 SCC 추출 int GetSCCsByDFS( int curr){ // … } int main(){ // 그래프 구축 scanf ( “%d %d” , & N, & M); for ( int i = 0 ; i < M; i + + ){ int A, B; scanf ( "%d %d" , & A, & B); // 양수냐 음수냐에 따라 각 정점 번호를 새로 매김 // x_k: (k-1)*2, not x_k: (k-1)*2-1 A = (A < 0 ? - (A + 1 ) * 2 : A * 2 - 1 ); B = (B < 0 ? - (B + 1 ) * 2 : B * 2 - 1 ); // (A or B)에 대한 간선 추가 adj[oppo(A)]. push_back (B); // not A -> B adj[oppo(B)]. push_back (A); // not B -> A } // SCC 추출 for ( int i = 0 ; i < N * 2 ; i + + ) if (dfsn[i] = = 0 ) GetSCCsByDFS(i); // x_k와 not x_k가 한 SCC 안에 있으면 불가능 for ( int i = 0 ; i < N; i + + ){ if (sn[i * 2 ] = = sn[i * 2 + 1 ]){ puts( "0" ); return 0 ; } } // 가능 puts( "1" ); } Colored by Color Scripter cs CNF를 입력받아 그걸 토대로 그래프를 구축하고, SCC별로 분리한 후 각 변수에 대해 자신과 not 형 변수가 같은 SCC 안에 있는 경우가 있는지 다 훑어봅니다. 그런 게 하나라도 있으면 불가능, 없으면 가능합니다. https://www.acmicpc.net/problem/11281 그럼 이제 나아가서, 각 변수에 어떤 값을 대입해야 f 식을 참으로 만들 수 있는지까지 알아봅시다. 이 솔루션을 얻어낼 수 있다면, f 식을 참으로 만들 수 있는지에 대한 조건이 정당하다는 것도 증명해낼 수 있겠죠. 아이디어는 아까 언급한대로, 명제 p → q가 있을 때 p가 거짓이라면 절대 이 명제를 해칠 일이 없다는 것에서 나옵니다. 이제 SCC 단위로는 안의 정점들이 다 같은 값을 가져야 한다는 것을 알았으니, 각 SCC를 하나의 정점으로 본다면 이런 발상이 가능합니다. SCC P, Q가 있을 때, P에서 Q로 가는 경로가 존재한다면, 만약 P의 정점들의 값이 거짓이라면 Q는 어찌되더라도 좋지만, P의 정점들의 값이 참이었다면 Q에 속한 정점들의 값은 무조건 참이어야만 합니다. 따라서 SCC 단위로 위상 정렬을 하여 훑어갈 때, 처음에 만나는 정점들의 값은 되도록 false로 설정해주고, 그 not 버젼의 정점을 true가 되게 하는 식으로 설정해 봅시다. q = ¬p라 할 때, p가 먼저 방문되었을 경우 p를 false로, q를 true로 설정하는 식으로 하면, p와 q는 서로 다른 SCC에 있고, p가 속한 SCC를 P, q가 속한 SCC를 Q라 하면 P에서 Q로 가는 경로야 있을 수 있지만 Q에서 P로 가는 경로는 없으므로 이런 방식이 먹힙니다. 즉, 이런 방식으로 값을 매기다가 참→거짓 꼴의 이동경로가 생기지 않습니다. 맨 처음에 {x4}와 {x1, x2, x3} 중 어떤 것이 방문될지는 모르지만, {x1, x2, x3}이 먼저 방문되었다고 칩시다. 앞서 말한 대로 x1, x2, x3을 굳이 true로 둘 이유가 없죠. false로 설정하는 것이 무조건 이득입니다. 그 다음, {¬x4}와 {x4} 중 어떤 게 먼저 방문될지 역시 알 수 없습니다. ① ¬x4가 먼저 방문된다면 우리는 ¬x4의 값을 false로 둘 것이기 때문에 x4는 true가 됩니다. 이 경우에 SCC {x4}로부터 들어가는 나머지 하나의 SCC {¬x1, ¬x2, ¬x3}은 이미 모두 true가 매겨져 있는데, 이는 앞에서 x1, x2, x3을 false로 정해두었기 때문. true → true로 가기 때문에 문제 없습니다. ② x4가 먼저 방문된다면 우리는 x4의 값을 false로 두게 됩니다. 이 경우에 {x1, x2, x3} → {¬x4}는 false → true고, {¬x4} → {¬x1, ¬x2, ¬x3}는 false → true가 되므로 역시 문제 없습니다. 따라서 어떤 경우라도 f 식은 참이 됩니다. 이 식 자체가 상당히 헐거웠네요. 같은 SCC 안에 모두 not이거나 모두 not이 아닌 변수들만 들어있어서 잘 와닿지 않을 수도 있는데, 확실히 이해하기 위해서는 둘이 섞인 예제를 생각해 보시면 좋을 것 같습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 int result[MAX]; // 각 변수의 값 (0, 1 중 하나) memset(result, - 1 , sizeof (result)); // 초기화 // 각 변수를 속해있는 SCC 번호순으로 정렬 P p[MAX * 2 ]; for ( int i = 0 ; i < N * 2 ; i + + ) p[i] = P(sn[i], i); sort(p, p + N * 2 ); // 놀랍게도, SCC 번호가 크면 클수록 DAG상에서 앞에 있음 for ( int i = N * 2 - 1 ; i > = 0 ; i – – ){ int var = p[i].second; // 아직 해당 변수값이 설정되지 않았다면 지금 설정 if (result[var / 2 ] = = – 1 ) result[var / 2 ] = ! (var% 2 ); } // 각 변수의 값 출력 for ( int i = 0 ; i < N; i + + ) printf ( "%d " , result[i]); cs 가능성 판별 후, 이런 추가적인 작업을 행해 주면 되는데, 여기서 SCC DAG의 위상 정렬 순서대로 정점을 방문하는 것을 놀랍도록 빠르게 할 수 있는데 종만북에서 언급한 위상 정렬 알고리즘이 DFS 방문 후 그 순서를 역순으로 뒤집으면 위상 정렬 순서가 되는 것이었습니다. DFS 방문 순서대로 발견되는 SCC 번호를 오름차순으로 매겼으니, 그 번호를 역순으로 방문하면 SCC 단위 위상 정렬 순서대로 방문하는 꼴이 되는 셈입니다. 이제 만나는 변수마다 먼저 마주친 쪽을 false로 설정해주면 되는데, 정점 x_k를 먼저 마주쳤다면 x_k = false가 되고, 정점 not x_k를 먼저 마주쳤다면 x_k = true가 됩니다. 또한, SCC 번호 순으로 변수를 방문하므로 하나의 SCC 안에 속한 변수들은 모두 연속적으로 방문되므로 항상 같은 값으로만 설정될 겁니다. 자 이쯤되면 슬슬 이런 의문이 나올 겁니다. 우리가 도대체 왜 이딴 짓을 했을까? 2-SAT 문제로 모델링하여 풀 수 있는 문제들이 존재하기 때문입니다. https://www.acmicpc.net/problem/2207 헌터x헌터 가위바위보라는 문제가 대표적인 2-SAT 문제입니다. 원장선생님이 3가지 선택지 중 보를 버리고, 가위와 바위 중 하나만 내겠다고 합니다. 또한 각 학생은 2번의 추측 중 한 개라도 맞히면 살 수 있고, 문제에서 묻는 것은 모든 학생이 살 수 있는 가능성이 존재하느냐입니다. 따라서 원장선생님이 k번째에 가위를 낼 경우 참이 되는 변수를 x_k라 합시다. x_k가 거짓이면 k번째에 바위를 냈다는 겁니다. 각 학생은 두 개의 예측 중 하나라도 맞혀야 하므로, 각 절을 각 학생에 대응시켜서 만들고 전체를 AND 연산하면 2-SAT 식이 완성됩니다. 예를 들면, 어떤 학생이 "원장선생님은 4번째에 바위를 내고 7번째에 가위를 내실 것이다"라고 예측했다면, 해당하는 절은 (¬x4 ∨ x7)로 표현할 수 있습니다. 각 절마다 하나 이상의 항이 참이 되어야 전체 식이 참이 되어서 모든 학생이 살 수 있게 되죠! 그럴 수 있는 경우가 절대 없다면 답이 OTL입니다. https://www.acmicpc.net/problem/3648 이 문제도 유사합니다. 각 심사위원이 2개의 의견을 내는데, 둘 중 최소한 하나는 반영이 되어야 한다고 합니다. 각 심사위원의 의견을 하나의 절에 대응시킬 수 있다는 게 보입니다. 헌데 이 문제의 경우 상근이에 해당하는 1번 참가자, 즉 x1 변수는 반드시 참이어야만 하는데, 이렇게 어떤 변수가 반드시 참이어야만 한다는 조건을 2-SAT 식에 잘 녹아들게 하려면 이런 절을 추가하면 됩니다. (x1 ∨ x1) 두 항 중 하나 이상이 참이어야 하는데, 둘이 똑같으니까 결국 x1이 참이어야만 한다는 소리죠. 이렇게 2-SAT 문제는 겉으로는 굉장히 알아채기 어렵게 꽁꽁 싸여 있는데, 보통 여러 사람이나 사물이 2개의 선택지를 가지고, 둘 중 최소한 하나는 만족해야 하는 형태의 조건들이 주어질 때 2-SAT을 생각해 볼 수 있습니다. 다른 SAT 문제들에 대해 짤막하게 말씀드리자면, 일단 1-SAT 문제는 매우 쉽습니다. 그냥 식에서 x1과 ¬x1이라던지, 자신과 not 형이 동시에 존재하지만 않으면 됩니다. 그러나 3-SAT 이상의 문제는 NP-Hard 영역에 속해 있는데요. 즉, 다항 시간에 푸는 방법이 아직은 발견되지 않았습니다. 그런데 3 이상의 k에 대해, k-SAT 문제는 항상 3-SAT 문제로 변형 가능하다는 것이 또 증명되어 있습니다. 현재로써는 2-SAT과 그 너머의 문제들의 난이도가 아주 확연히 차이가 나고 있죠. 추천 문제 11280번: 2-SAT - 3 위에서 설명한 문제입니다. 11281번: 2-SAT - 4 위에서 설명한 문제입니다. 2207번: 가위바위보 위에서 설명한 문제입니다. 3648번: 아이돌 위에서 설명한 문제입니다. 3747번: 완벽한 선거! 설문조사 결과가 아주 2-SAT에 맞게 잘 들어오고 있습니다. 항상 둘 중 하나라도 만족했으면 좋겠다는 뜻입니다. 각 후보마다 당선되면 참, 낙선하면 거짓인 변수를 만들어서 풀면 됩니다. 7535번: A Bug's Life k번째 벌레가 수컷이면 true, 암컷이면 false라던가 아니면 반대인 변수 x_k들을 만들고, p번 벌레와 q번 벌레가 의사소통을 했을 때 서로의 성별이 다르다는 의미에서 ¬x_p → x_q, x_p → ¬x_q, ¬x_q → x_p, x_q → ¬x_p 이렇게 4개의 명제를 그래프에 추가해 줍니다. 한쪽의 성별만 결정되어도 다른 쪽의 성별 또한 결정된다는 의미입니다. ¬x_p → x_q, x_q → ¬x_p 이렇게 양방향으로 명제가 존재하므로, x_p와 x_q가 둘 다 거짓이거나 참일 수가 없습니다. 어찌보면 XOR 연산을 풀어서 쓴 것입니다. 15675번: 괴도 강산 (★) 제가 돌의 정령으로 등장하는 문제입니다. 돌의정령 커여워... 2-SAT인지 모르면 접근하기 어려운 문제로, 먼저 똑같은 행이나 열을 두 번 이상 지나갈 필요는 전혀 없습니다. 보석이 있는 칸은 해당하는 행과 열 중 정확히 한 개를 지나야 하고, 위치추적기가 있는 칸은 해당하는 행과 열 중 0개 또는 2개를 지나야 합니다. 이 모든 조건은 각 행, 열을 하나의 변수로 두면 2-SAT으로 모델링해서 풀 수 있습니다. 16915번: 호텔 관리 (★) 각 방마다 두 개의 스위치에만 연결되어 있으므로, 방의 초기 상태가 꺼져 있으면 두 스위치 중 하나만, 켜져 있으면 두 스위치가 둘 다 켜지거나 꺼지면 됩니다. 11668번: 파이프 청소 (★) 교차하는 파이프들마다, 둘 중 정확히 한 쪽에만 로봇이 지나가야 합니다. 각 파이프 쌍마다 교차하는지 검사한 후, 교차하면 XOR 절을 세워서 풀 수 있습니다. 1739번: 도로 정비하기 (★) 평소보다 고려해야 할 조건이 많습니다. 두 마을의 위치의 x, y좌표 중 같은 것이 있다면 케이스가 쉬워지므로 둘 다 다른 경우를 살펴보겠습니다. 일단 도로의 방향을 고려하지 않는다면, A

[그래프] 2-SAT문제 – 1

2-SAT문제란?

2-SAT(2-SATisfiability)문제는 충족 가능성 문제(satisfiability problem)의 한 종류입니다.

충족 가능성 문제란, 여러 개의 boolean변수들로 이루어진 식이 있을 때 각 변수에 값을 할당하여 식을 참으로 만드는 조합을 찾거나, 그러한 조합이 없음을 찾는 문제입니다.

2-SAT문제는

(a 1 ∨ b 1 ) ∧ (a 2 ∨ b 2 ) ∧ … ∧ (a m ∨ b m )

위와 같은 논리식에서 식을 참으로 만드는 변수 값의 조합을 찾거나, 그러한 조함이 없음을 찾는 것을 목표로 합니다.

아래 식을 봅시다.

f = (x 2 ∨ ￢x 1 ) ∧ (￢x 1 ∨ ￢x 2 ) ∧ (x 1 ∨ x 3 ) ∧ (￢x 2 ∨ ￢x 3 ) ∧ (x 1 ∨ x 4 )

이 식은 {x1 : false, x2 : false, x3 : true, x4 : true} 인 경우에 참이 됩니다.

하지만 아래 식은 어떻게 할당하든 항상 거짓이 됩니다.

f = (x 1 ∨ x 2 ) ∧ (x 1 ∨ ￢x 2 ) ∧ (￢x 1 ∨ x 3 ) ∧ (￢x 1 ∨ ￢x 3 )

x1을 true라고 잡으면 x3과 ￢x3 모두 참이 되어야 하고, x1을 false라고 잡으면 x2와 ￢x2 모두 참이 되어야 하기 때문에 항상 거짓이 된다는 것을 알 수 있습니다.

해결 방법

이제, 2-SAT문제를 어떻게 푸는지 알아봅시다.

2-SAT문제에서 주어지는 식은 그래프로 나타낼 수 있습니다. 각 정점들은 x i 와 ￢x i 에 대응됩니다.

정점은 각 변수와 그의 부정형에 대응시킨다고 했으니, 이제 간선을 잘 이어주면 됩니다. (x i ∨ x j )를 봅시다.

만약 x i 가 false라면 x j 는 true가 나와야 합니다.

반대로 x j 가 false라면 x i 는 true가 나와야 합니다.

그러므로 ￢x i → x j 와 ￢x j → x i , 두 개의 간선을 만들어줍시다. 이는 어느 하나가 거짓이라면, 반드시 다른 하나는 참이 되어야 한다는 것을 의미합니다.

주어진 식이 참이 되도록 하는 변수 값의 조합의 존재 여부는 위에서 모델링한 그래프에 따라 결정이 됩니다.

가능한 경우는 x i 와 ￢x i 가 같은 SCC에 속하는 일이 없는 경우와 동치입니다.

만약 같은 SCC에 속해있다면, x i 에서 ￢x i 로 가는 경로, ￢x i 에서 x i 로 가는 경로가 모두 존재한다는 것을 의미합니다. 따라서 x i 와 ￢x i 모두 참이 되어야 하지만 불가능합니다.

그러므로 참이 되도록 하는 조합의 존재 여부는 SCC 알고리즘을 이용해 구할 수 있습니다.

구현

icpc.me/11280 문제(2-SAT – 3)는 아래 코드를 이용해 풀 수 있습니다.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66 #include using namespace std ; vector < int > gph [ 20202 ], rev [ 20202 ]; inline int notX ( int x ){ return x ^ 1 ; } inline int trueX ( int x ){ return x << 1 ; } inline int falseX ( int x ){ return x << 1 | 1 ; } int visit [ 20202 ]; vector < int > dfn ; int scc [ 20202 ]; void dfs ( int v ){ visit [ v ] = 1 ; for ( auto u : gph [ v ]) if ( ! visit [ u ]) dfs ( u ); dfn . push_back ( v ); } void revdfs ( int v , int color ){ visit [ v ] = 1 ; scc [ v ] = color ; for ( auto u : rev [ v ]) if ( ! visit [ u ]) revdfs ( u , color ); } void getSCC ( int n ){ memset ( visit , 0 , sizeof visit ); for ( int i = 1 * 2 ; i <= n * 2 + 1 ; i ++ ){ if ( ! visit [ i ]) dfs ( i ); } memset ( visit , 0 , sizeof visit ); reverse ( dfn . begin (), dfn . end ()); int cnt = 1 ; for ( auto i : dfn ){ if ( ! visit [ i ]){ revdfs ( i , cnt ); cnt ++ ; } } } int main (){ ios_base :: sync_with_stdio ( 0 ); cin . tie ( 0 ); int n , m ; cin >> n >> m ; for ( int i = 0 ; i < m ; i ++ ){ int a , b ; cin >> a >> b ; if ( a > 0 ) a = trueX ( a ); else a = falseX ( – a ); if ( b > 0 ) b = trueX ( b ); else b = falseX ( – b ); gph [ notX ( a )]. push_back ( b ); gph [ notX ( b )]. push_back ( a ); rev [ b ]. push_back ( notX ( a )); rev [ a ]. push_back ( notX ( b )); } getSCC ( n ); for ( int i = 1 ; i <= n ; i ++ ){ if ( scc [ trueX ( i )] == scc [ falseX ( i )]){ cout << "0" ; return 0 ; } } cout << "1" ; } 추천 문제 http://icpc.me/11280 위에서 설명한 문제입니다. http://icpc.me/3747 http://icpc.me/3748 http://icpc.me/2207 모두 동일한 문제입니다. 음수는 부정형으로 취급한 뒤 CNF식을 세우면 됩니다. http://icpc.me/2519 풀이 다음 글에서는 2-SAT문제에서 각 변수의 값을 구하는 방법을 알아보겠습니다.

충족 가능성 문제

충족 가능성 문제(充足可能性問題, satisfiability problem, SAT)는 어떠한 변수들로 이루어진 논리식이 주어졌을 때, 그 논리식이 참이 되는 변수값이 존재하는지를 찾는 문제이다. 만족성 문제, 만족도 문제, 만족 문제, 불린 충족 가능성 문제(boolean satisfiability problem)라고도 부른다.

기본 정의 [ 편집 ]

논리식은 기본적으로 진리값을 취하는 논리 변수 x 1 , x 2 ⋯ {\displaystyle x_{1},x_{2}\cdots } 와 몇몇 논리 연산자 결합에 의해 만들어지는 유한한 길이의 식을 가리킨다. 여기에서 사용되는 연산자는 다음과 같다.

논리 부정, ( x 1 ¯ ) {\displaystyle ({\overline {x_{1}}})} x 1 {\displaystyle x_{1}}

논리합, ( x 1 ∨ x 2 ) {\displaystyle (x_{1}\lor x_{2})} x 1 {\displaystyle x_{1}} x 2 {\displaystyle x_{2}}

논리곱, ( x 1 ∧ x 2 ) {\displaystyle (x_{1}\land x_{2})} x 1 {\displaystyle x_{1}} x 2 {\displaystyle x_{2}}

또한, 논리식에서 각각의 x i {\displaystyle x_{i}} , x i ¯ {\displaystyle {\overline {x_{i}}}} 식을 리터럴(literal)이라고 부른다. 여러 리터럴의 논리합, 즉 x 1 ∨ x 2 ∨ ⋯ ∨ x i {\displaystyle x_{1}\lor x_{2}\lor \cdots \lor x_{i}} 꼴로 이루어진 식을 클로저(clause), 절이라고 정의한다. 클로저들의 논리곱으로 표현되어 있는 논리식을 논리곱 표준형(CNF)이라고 부른다.

계산 복잡도 [ 편집 ]

충족 가능성 문제의 결정 문제는 NP-완전에 속한다. 이것은 스티븐 쿡이 증명했으며(쿡-레빈 정리), 이 문제는 NP-완전이라는 것이 증명된 최초의 문제이기도 하다. 또한, 논리식이 논리곱 표준형으로 이루어진 경우에도 역시 NP-완전에 속한다.

k-충족 가능성 문제, k-SAT는 각 클로저에 들어있는 리터럴의 개수가 k개 이하로 구성된 CNF 논리식만 입력으로 받는 문제이다. 예를 들어 3-SAT는 한 절에 들어가는 리터럴 개수를 3개 이하로 제한하는 문제이다. 3-SAT도 마찬가지로 NP-완전 문제이다. 리터럴 개수를 정확히 3개로만 제한하는 문제는 EXACT 3-SAT이라고 하며, 모든 SAT 문제는 다항 시간에 3-SAT 또는 EXACT 3-SAT로 환산(Reduction)될 수 있다.

반면, 2-SAT, CNF에서 한 절에 들어가는 리터럴 개수가 2개 이하인 문제는 P에 속한다. 즉, 다항 시간에 풀 수 있다.

2-SAT 및 그의 응용

#include #include #include #include using namespace std ; int N , M ; typedef vector < int > vi ; typedef vector < vi > vvi ; typedef pair < int , int > pii ; inline int bmod ( int x , int y ) { return ( x + y ) % y ; } // Kosaraju’s SCC Algorithm vvi reverse_edges ( vvi & adj ) { vvi adj_rev ; adj_rev . resize ( adj . size ()); for ( int i = 0 ; i < adj . size (); i ++ ) { int u = i ; for ( int j = 0 ; j < adj [ i ]. size (); j ++ ) { int v = adj [ i ][ j ]; adj_rev [ v ]. push_back ( u ); } } return adj_rev ; } void DFS ( vvi & adj , int u , vi & visited , vi & node_stack ) { visited [ u ] = 1 ; for ( int i = 0 ; i < adj [ u ]. size (); i ++ ) { int v = adj [ u ][ i ]; if ( visited [ v ] == 0 ) DFS ( adj , v , visited , node_stack ); } node_stack . push_back ( u ); } vvi find_SCC ( vvi & adj , vvi & adj_rev ) { vi vis_fw ; vi nd_st ; vis_fw . resize ( adj . size (), 0 ); for ( int i = 0 ; i < adj . size (); i ++ ) { if ( vis_fw [ i ] == 0 ) DFS ( adj , i , vis_fw , nd_st ); } vi vis_bw ; vvi sccs ; vis_bw . resize ( adj_rev . size (), 0 ); for ( int i = 0 ; i < adj_rev . size (); i ++ ) { int u = nd_st . back (); nd_st . pop_back (); if ( vis_bw [ u ] == 0 ) { vi scc ; DFS ( adj_rev , u , vis_bw , scc ); sccs . push_back ( scc ); } } return sccs ; } // Reducing 2-SAT into SCC void build_graph ( vector < pii > & P , vvi & adj ) { int k = P . size (); int n = N ; adj . resize ( 2 * n ); vi perm ; perm . push_back ( 0 ); for ( int i = 1 ; i < n + 1 ; i ++ ) perm . push_back ( n - 1 + i ); perm . push_back ( 0 ); for ( int i = n ; i > 0 ; i — ) perm . push_back ( n – i ); int m = perm . size (); for ( int j = 0 ; j < k ; j ++ ) { int u = P [ j ]. first , v = P [ j ]. second ; adj [ perm [ bmod ( - u , m )]]. push_back ( perm [ bmod ( v , m )]); adj [ perm [ bmod ( - v , m )]]. push_back ( perm [ bmod ( u , m )]); } } // 2-SAT Solver vi solve ( vector < pii > & P ) { vvi adj , adj_rev ; int n = N ; build_graph ( P , adj ); adj_rev = reverse_edges ( adj ); vvi sccs = find_SCC ( adj , adj_rev ); vi sccID ; sccID . resize ( 2 * n + 5 ); int m = sccID . size (); for ( int h = 0 ; h < sccs . size (); h ++ ) { for ( int i = 0 ; i < sccs [ h ]. size (); i ++ ) { int c = sccs [ h ][ i ]; if ( n <= c ) c -= n - 1 ; else c -= n ; sccID [ bmod ( c , m )] = h ; } } vi ans ; for ( int i = 1 ; i < n + 1 ; i ++ ) { if ( sccID [ i ] == sccID [ m - i ]) return ans ; } for ( int i = 1 ; i < n + 1 ; i ++ ) ans . push_back (( sccID [ i ] > sccID [ m – i ])); return ans ; } // Input/Output int main (){ scanf ( “%d%d” , & N , & M ); vector < pii > P ; for ( int num = 0 ; num < M ; num ++ ) { int i , j ; scanf ( "%d%d" , & i , & j ); P . push_back ( make_pair ( i , j )); } vi ans = solve ( P ); if ( ans . empty ()) { printf ( "0 " ); return 0 ; } printf ( "1 " ); for ( int i = 0 ; i < N ; i ++ ) printf ( "%d " , ans [ i ]); return 0 ; }

[알고리즘 문제 모음] 2-SAT (2 – Satisfiability Problem, 충족 가능성 문제)

반응형

*문제들의 난이도 분류는 종만북 혹은 solved.ac 출처임을 밝힙니다.*

★ 문제는 작성자가 다시 풀어보고 싶은 문제 혹은 어려웠던 문제입니다.

+가 붙은 문제는 해당 문제에서 중요하게 생각하는 부분입니다.

2-SAT 해설

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

2-SAT 문제 목록

[백준] 2 – SAT – 3(11280) – Platium 4

[백준] 2 – SAT – 4(11281) ★ + 답 출력하기 – Platium 3

[백준] 아이돌(3648) ★ – Platium 4

[백준] 호텔 관리(16915) + 식 세우기 – Platium 3

반응형

16992번: 3-SAT

문제

3-SAT은 N개의 불리언 변수 \(x_1, x_2, …, x_n\)가 있을 때, 3-CNF 식을 true로 만들기위해 \(x_i\)를 어떤 값으로 정해야하는지를 구하는 문제이다.

3-CNF식은 \( \left( x \lor y \lor \lnot z\right) \land \left( x \lor \lnot y \lor z \right) \land \left( \lnot w \lor x \lor \lnot z \right) \land \left( x \lor z \lor y \right) \) 와 같은 형태이다. 여기서 괄호로 묶인 식을 절(clause)라고 하는데, 절은 3개의 변수를 \(\lor\)한 것으로 이루어져 있다. \(\lor\)는 OR, \(\land\)는 AND, \(\lnot\)은 NOT을 나타낸다.

변수의 개수 N과 절의 개수 M, 그리고 식 \(f\)가 주어졌을 때, 식 \(f\)를 true로 만들 수 있는지 없는지를 구하는 프로그램을 작성하시오.

예를 들어, N = 3, M = 4이고, \(f = \left( \lnot x_1 \lor x_2 \lor x_3 \right) \land \left( \lnot x_1 \lor \lnot x_2 \lor x_3 \right) \land \left( x_1 \lor \lnot x_2 \lor x_3 \right) \land \left( x_3 \lor \lnot x_2 \lor \lnot x_1 \right) \) 인 경우에 \(x_1\)을 false, \(x_2\)을 false, \(x_3\)를 true로 정하면 식 \(f\)를 true로 만들 수 있다. 하지만, N = 1, M = 2이고, \(f = \left( x_1 \lor x_1 \lor x_1 \right) \land \left( \lnot x_1 \lor \lnot x_1 \lor \lnot x_1 \right) \)인 경우에는 \(x_1\)에 어떤 값을 넣어도 식 f를 true로 만들 수 없다.

2-SAT(2-CNF Satisfiability Problem)

여기, 여기, 여기, 여기 참조

수학적인 기초

먼저 절, 명제, 조건문 이 세가지가 헷갈리기 쉬운데, 이 알고리즘을 이해하려면 절대 헷갈리면 안된다.

절은 나중에 설명하고 명제부터 살펴보자.

명제란 대한민국의 수도는 서울이다, 사람은 날 수 있다. 처럼 true/false를 특정지을 수 있는 것을 말한다.

나는 사람이다. 라는 명제를 P로 놓고, 나는 동물이다. 라는 명제를 Q로 놓은 다음 화살표로 연결하면

P->Q 이렇게 되고 조건문이된다.

조건문의 true/false는 생각보다 까다로운데 명제논리 링크를 참조해서 이해해보자.

P Q P → Q T T T T F F F T T F F T

위에서 다른건 다 상식선에서 이해가 되는데 P가 거짓이면 Q가 참이던 거짓이던 모순이 없는건 일상생활 명제에 대입하면 좀 받아들이기 힘들다.

(철희가 남자라면 철희는 남자가 아니다. 라는 조건문도 모순이 없는 참이 되어버리는 사태가 발생한다. 근데 생각해보면 남자라면 이라는게 거짓일때만 모순이 없는것이므로, 남자라는게 뻥이었으므로 뻥이 아닌 사실로는 남자일수도 있고 아닐수도 있는 상태가 되는걸로 이해는 가능하다. )

그럴때는 다음 문장을 참고해서 대략적으로 이해하고 넘어가자

P가 거짓일 때 참이되는 것이 아직 받아들이기 어렵다면 이렇게 생각해보자. 선생님이 학생에게 ‘체육대회에서 100m를 5초안에 뛸 수 있으면 72 km/h… 아이스크림을 주겠다’라고 말했다고 해보자. 이 말이 거짓말이 되는 경우는 “단 한가지” 뿐이다. 즉, (2) 학생이 100m를 5초 안에 들어왔는데 선생님이 아이스크림 안주는 경우만 거짓 이다. (3) 학생이 5초안에 못뛰었을 때 선생님이 학생이 안쓰러워 아이스크림을 사준 경우 이는 선생님이 약속을 어겼다고 볼 수 없고 단순한 변심으로 보는게 타당할 것이다. 즉 위의 선생님의 약속(가언 명제) 자체는 여전히 참 이다. 그리고 마찬가지로 (4) 5초안에 못뛰었을 때 선생님이 아이스크림을 사주지 않는 경우 학생은 그런가보다 하고 넘어갈 수 있고 이 또한 선생님이 약속(가언 명제)을 어겼다고 할 수 없다. 즉, 참 으로 인정한다. 다시 정리하자면 학생이 100m를 5초 안에 뛰지 못한 경우에 대해서 선생님은 어떠한 약속도 하지않았으므로 선생님이 어떤 행동을 하든 약속이 거짓말이 될 수없다. [12]

2SAT이란

2-SAT(2-SATisfiability)문제는 충족 가능성 문제(satisfiability problem)의 한 종류입니다.

충족 가능성 문제란, 여러 개의 boolean변수들로 이루어진 식이 있을 때 각 변수에 값을 할당하여 식을 참으로 만드는 조합을 찾거나, 그러한 조합이 없음을 찾는 문제입니다.

f = (x2 ∨ ￢x1) ∧ (￢x1 ∨ ￢x2) ∧ (x1 ∨ x3) ∧ (￢x2 ∨ ￢x3) ∧ (x1 ∨ x4)

이 식은 {x1 : false, x2 : false, x3 : true, x4 : true} 인 경우에 참이 됩니다.

가만 보면, 나이브한 솔루션은 x1~x4값에 대해서 0과1을 대입해보는 식으로 2^n의 모든 부분집합을 테스트해보면 된다는 사실을 알 수 있다.

위에보면 괄호안에 두개의 변수가 들어있는데, 그래서 2-SAT이고, 괄호하나를 절(clause)이라고 부른다.

괄호안은 항상 OR 연산자, 괄호밖은 항상 AND연산자로 되어 있다.

이렇게 절의 AND 연산으로만 표현된 식의 형태를 CNF(Conjunctive Normal Form)라고 합니다.

1SAT문제는 트리비얼하게 O(N)에 풀린다.

3SAT이상은 다항시간 솔루션이 없다.

신기하게도 2SAT문제도 선형시간에 풀린다!

여기까지만 들으면 이런걸 왜 보고 있나하는 생각이 드는데, 의외로 많은 문제들이 2-SAT으로 변환 가능하고, SCC로 풀수 있다고 한다.

여기 참조

1. 답이 존재하는지 여부 구하기

여기까지는 할만한 느낌

핵심아이디어

1. 논리식을 조건문으로 바꾼다 : (A∨B) = ¬A → B 와 ¬B → A !!

A가 거짓이라면 B는 무조건 참이여야 하며, B가 거짓이라면 A는 무조건 참이여야 한다.

2. 모든 절의 명제들을 합하여 하나의 유향그래프를 생성할 수 있다.

3. 사이클 전체가 true이거나 전체가 false로 통일되어야한다. A와 ¬A이 같은 사이클에 있을 수 없다.

P Q P → Q T T T T F F F T T F F T

3번을 잘 이해해야 하는데, true -> false이면(사실 그럴때만) 조건문에 모순이 생긴다는 걸 기억하면 된다.

(p → q에서 p가 참일 때는 q는 무조건 참이여야하며 p가 거짓일 때는 q가 무엇이든지 상관없음)

따라서, A→¬A가 나오면 A는 반드시 false여야 한다.

마찬가지로 ¬A→A가 나오면 A는 반드시 true여야 함

근데 (하나의 사이클에서 ) A→¬A도 발견되고 ¬A→A도 발견된다? 그럼 false도 될수 없고, true도 될수 없어서 모순!

(여기서 한가지 중요한 관찰은 같은 SCC가 아니면서 A→¬A 또는 ¬A→A 이렇게 단방향은 있을 수 있다는 것이다. 일상언어 조건문으로 바꾸면 남자이면 남자가 아니다. 이런게 되어서 무지 이상하지만, 상단에 서술했듯이 수학적으로는 모순이 없다. 조건문 왼쪽에 거짓이기만 한다면.)

내 코드는 다음과 같다. 이 문제의 답안이기도 하다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 #include < bits / stdc + + .h > using namespace std ; #define REP(i,n) for ( int i = 0 ;i < ( int )(n);i + + ) #define REP1(i,n) for ( int i = 1 ;i < = ( int )(n);i + + ) using vi = vector < int > ; using vvi = vector < vi > ; struct result { vi scc_map; vvi scc_list; vvi scc_adj_list; }; result scc_dag_kosaraju( int max_v, vvi & adj_list, vvi & adj_rlist, int base1) { // step1. dfs로 방문하며 말단부터 stack push vi visit(max_v + base1); stack < int > S; function < void ( int n) > dfs = [ & ]( int n) { if (visit[n]) return ; visit[n] = 1 ; for ( int a : adj_list[n]) dfs(a); S.push(n); }; for ( int i = base1; i < max_v + base1; i + + ) if (visit[i] = = 0 ) dfs(i); // step2. stack에서 꺼내면서 // 역방향으로 접근가능한 정점들을 SCC로 판정 visit.clear(); visit.resize(max_v + base1); vi scc(max_v + base1); // map. scc[v]=1 이면 v정점은 1번 SCC에 속한다고 하는것 int scc_ix = base1; vvi scc_list; if (base1) scc_list. push_back (vi()); while (S. size ()) { int n = S.top(); S. pop (); if (visit[n]) continue ; vi sl; function < void ( int n) > dfs = [ & ]( int n) { if (visit[n]) return ; visit[n] = 1 ; scc[n] = scc_ix; sl. push_back (n); for ( auto a : adj_rlist[n]) dfs(a); }; dfs(n); scc_list. push_back (sl); scc_ix + + ; } vvi scc_adj_list(scc_ix); for ( int u = base1; u < max_v + base1; u + + ) { for ( auto v : adj_list[u]) { if (scc[u] ! = scc[v]) { //cout << scc[u] << ' ' << scc[v] << endl; scc_adj_list[scc[u]]. push_back (scc[v]); } } } return { scc, scc_list, scc_adj_list}; } int32_t main() { ios::sync_with_stdio( false ); cin .tie( 0 ); int N, M; cin > > N > > M; vvi adj_list( 2 * N + 2 ), adj_list2( 2 * N + 2 ); for ( int i = 0 ;i < M;i + + ) { int a, b; cin > > a > > b; if (a < 0 ) a * = - 2 ; else a = a * 2 - 1 ; if (b < 0 ) b * = - 2 ; else b = b * 2 - 1 ; int na = (a % 2 = = 0 ) ? a - 1 : a + 1 ; int nb = (b % 2 = = 0 ) ? b - 1 : b + 1 ; //not a -> b adj_list[na]. push_back (b); adj_list2[b]. push_back (na); // 역방향 //not b -> a adj_list[nb]. push_back (a); adj_list2[a]. push_back (nb); // 역방향 } auto r = scc_dag_kosaraju(N * 2 + 1 , adj_list, adj_list2, true ); int ok = 1 ; for ( int i = 1 ;i < = N;i + + ) { if (r.scc_map[i * 2 ] = = r.scc_map[i * 2 - 1 ]) ok = 0 ; } cout < < ok < < ' ' ;; return 0 ; } Colored by Color Scripter cs 2. 유효한 변수값들 구하기 난이도가 확 올라가는 느낌 여기, 여기 참조 추가로 필요한 아이디어 모든 정점에 대해서 위상정렬 순으로 처음만나면 거짓을 만들어주는식으로 채워주면 된다. 예를 들어 위상정렬순으로 not X3을 먼저 만났으면 not X3 = false 가 되어야 하므로 X3은 true로 확정해주는 식. 이런방법 말고도 굉장히 많은 방법이 있는것 같은데, 적당히 한가지로 외워두면 될듯하다. 아래는 내 코드고, 이 문제에 대한 답안이기도 하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 #include < bits / stdc + + .h > using namespace std ; #define REP(i,n) for ( int i = 0 ;i < ( int )(n);i + + ) #define REP1(i,n) for ( int i = 1 ;i < = ( int )(n);i + + ) using vi = vector < int > ; using vvi = vector < vi > ; struct result { vi scc_map; vvi scc_list; }; result scc_dag_tarjan(vvi & adj_list, int base1) { int max_v = ( int )adj_list. size () – 1 ; // base1==0일때 테스트 안됨! //타잔은 수행후 SCC들이 역순으로 위상정렬을 이루므로, //그 성질을 이용하면 좋다(2-SAT등) vvi ans; stack < int > S; //아래에서 visit는 ord와 통합가능하지만, 가독성을 위해 남겨둠 vi scc_map(max_v + base1, – 1 ), visit(max_v + base1), ord(max_v + base1), parent(max_v + base1); int g_ix = 0 ; // 코사라주나 단절선 구하는것과 다르게 finish 운영해줌 // 일반적으로 finish배열이 dfs리턴할때 true해주는것과 다르게 // SCC분리가 끝났음을 의미 vi finish(max_v + base1); static int scc_ix = base1; function < int ( int ) > dfs = [ & ]( int n) – > int // low를 리턴 { visit[n] = 1 ; ord[n] = + + g_ix; int low = ord[n]; S.push(n); // 스택에 먼저 푸시 for ( auto adj : adj_list[n]) { if (visit[adj] = = 0 ) // tree edge 의 경우 { int r = dfs(adj); // 단절점 로직의 경우 여기서 자식트리중 하나라도 자신위로 올라가지 못하면 단절점으로 판정하지만 // SCC 타잔에서는 그러한 로직은 없고, 루프하단에 result == ord[n] 으로 // 자신포함 자식트리중 도달가능한 가장 높은 정점이 자신일 경우 SCC 추출하는 로직으로 바뀐다. // if (r > ord[n]) ans.insert({ min(n,adj), max(n,adj) }); low = min(low, r); } // 방문은 했으나 아직 SCC로 추출되지는 않은 이웃 else if (finish[adj] = = 0 ) // back edge 또는 cross edge의 일부 low = min(low, ord[adj]); // 접근가능한 백정점 순서로 업데이트 } // 자신포함 자식트리중 도달가능한 가장 높은 정점이 자신일 경우 SCC 추출 if (low = = ord[n]) { vi scc; while (S. size ()) { int a = S.top(); S. pop (); scc. push_back (a); scc_map[a] = scc_ix; finish[a] = 1 ; if (a = = n) break ; } sort(scc. begin (), scc. end ()); ans. push_back (scc); scc_ix + + ; } return low; }; for ( int i = base1; i < max_v + base1; i + + ) if (visit[i] = = 0 ) dfs(i); return { scc_map, ans }; } #define DBL(a) ( 2 * (a)) #define CONV(a) (a) < 0 ?(a) * - 2 :(a) * 2 + 1 int32_t main() { ios::sync_with_stdio( false ); cin .tie( 0 ); int N, M; cin > > N > > M; vvi adj_list(DBL(N + 1 )); for ( int i = 0 ; i < M; i + + ) { int a, b; cin > > a > > b; a = CONV(a); b = CONV(b); //nice magic property! int na = a ^ 1 ; int nb = b ^ 1 ; //not a -> b adj_list[na]. push_back (b); //not b -> a adj_list[nb]. push_back (a); } auto r = scc_dag_tarjan(adj_list, true ); for ( int i = 1 ; i < = N; i + + ) { if (r.scc_map[CONV(i)] = = r.scc_map[CONV( - i)]) { cout < < 0 < < ' ' ; return 0 ; } } // 여기까지 오면 변수조합이 있는건 보장된다. 모순만 없도록 배열해주면 됨 cout < < 1 < < ' ' ; for ( int i = 1 ; i < = N; i + + ) { // 아랫부분 아직 제대로 이해 못한 상태 ㅠ // 소스가 워낙 간결해서 일단 채택은 해 두었다. cout < < (r.scc_map[CONV(i)] < r.scc_map[CONV( - i)]) < < ' ' ; } return 0 ; } Colored by Color Scripter cs 반응형

Algorithm in A..Z

반응형

개념

충족 가능성 문제 중 하나로써 아래와 같은 형태를 2-SAT 문제라 한다.

* 충족 가능성 문제 : Boolean으로 이루어진 식이 있을 때 해당 식이 True인 경우를 찾는 문제

f=(¬x1∨x2)∧(¬x2∨x3)∧(x1∨x3)∧(x3∨x2) 인 경우에 f를 true로 만드는 경우 ¬ : NOT ∨ : OR ∧ : AND

괄호 안의 OR 연산으로 이루어진 것을 절(Clause)이라고 표현하고 AND와 절로 이루어진 식을 CNF(Conjunctive Normal Form)라고 한다.

각 절의 변수의 개수가 2개면 2-SAT이라 하고 N개면 N-SAT이라고 한다. 2개 같은 경우 SCC 알고리즘을 사용하여 쉽게 해결할 수 있지만, 3개 이상의 SAT 문제에서는 NP-Hard 문제이다.

작동원리

1. 각 절을 바탕으로 그래프를 작성한다.

(x1∨x2) 절이 있을 때 x1이 False면 x2는 True인게 자명하다. (x2가 False면 x1이 True인 것도 자명하다.)

각 변수와 NOT인 변수를 정점으로 보고 ¬x1→x2, ¬x2→x1의 명제를 간선으로 생각하여 그래프를 작성한다.

2. SCC 알고리즘을 사용하여 SCC를 구한다.

3. x와 ¬x이 같은 SCC에 있는 경우 2-SAT을 해결할 수 없다. (¬x⇒x은 모순이기 때문에)

4. 해결할 수 있는 경우 x의 SCC 번호가 ¬x의 번호보다 작은 경우 x는 True이다.

특징

p → q라는 명제가 있을 때

1) p가 참이면 q는 무조건 참이여야 한다.

2) p가 거짓이면 q는 참, 거짓 상관없다.

=> 각 변수들의 참, 거짓을 알고 싶을 때 위상 정렬을 진행한 후 방문하지 않은 정점에 False를 우선으로 대입하면서 변수들의 참, 거짓을 알 수 있다.

하나의 SCC 안에 속한 변수들은 모두 연속적으로 방문되므로 항상 같은 값으로만 설정될 겁니다.

시간 복잡도

1. SCC 알고리즘을 사용할 때 O(V + E)

O(V + E)

문제

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

코드

#include using namespace std; constexpr int NONE = -1; int n, m; vector> graph; inline int convert(int value) { return value <= n ? value + n : value - n; } int order; stack st; vector sccNumber, isVisited; vector> scc; int dfs(int index) { st.push(index); isVisited[index] = order++; int value = isVisited[index]; for (auto &next : graph[index]) { if (isVisited[next] == NONE) { value = min(value, dfs(next)); } else if (sccNumber[next] == NONE) { value = min(value, isVisited[next]); } } if (value == isVisited[index]) { vector cycle; while (!st.empty()) { int i = st.top(); st.pop(); cycle.push_back(i); sccNumber[i] = (int)scc.size(); if (i == index) { break; } } scc.push_back(cycle); } return value; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> m; graph.resize(2*n + 1); sccNumber.resize(2*n + 1, NONE); isVisited.resize(2*n + 1, NONE); while (m–) { int s, e; cin >> s >> e; s = s < 0 ? convert(-s) : s; e = e < 0 ? convert(-e) : e; graph[s].push_back(convert(e)); graph[e].push_back(convert(s)); } for (int i = 1;i <= 2*n;++i) { if (isVisited[i] == NONE) { dfs(i); } } for (int i = 1;i <= n;++i) { if (sccNumber[i] == sccNumber[convert(i)]) { cout << 0 << " "; return 0; } } cout << 1 << " "; for (int i = 1;i <= n;++i) { cout << (sccNumber[i] >= sccNumber[convert(i)]) << " "; } } 반응형

키워드에 대한 정보 sat 문제 알고리즘

다음은 Bing에서 sat 문제 알고리즘 주제에 대한 검색 결과입니다. 필요한 경우 더 읽을 수 있습니다.

이 기사는 인터넷의 다양한 출처에서 편집되었습니다. 이 기사가 유용했기를 바랍니다. 이 기사가 유용하다고 생각되면 공유하십시오. 매우 감사합니다!

사람들이 주제에 대해 자주 검색하는 키워드 SAT 문제

• SAT
• propositional logic
• computer science
• automated reasoning
• artifitial intelligence

SAT #문제

---

YouTube에서 sat 문제 알고리즘 주제의 다른 동영상 보기

주제에 대한 기사를 시청해 주셔서 감사합니다 SAT 문제 | sat 문제 알고리즘, 이 기사가 유용하다고 생각되면 공유하십시오, 매우 감사합니다.