devbelly

문제 www.acmicpc.net/problem/17038 알고리즘 2-SAT 풀이 소들마다 두 개의 목초지에서 식사를 하고, 소들의 식성은 두가지로 나뉩니다. 한 식성은 두 목초지의 풀이 같아야만 하고, 다른 식성은 두 목초지의 풀이 달라야만 식사를 합니다. 이 때, 가능한 목초지의 경우의 수를 구하는 문제입니다. 두 종류의 풀이 주어지는 점, 이를 동시에 만족하도록 하는 점에서 2-SAT임을 파악하여 풀도록 합시다. 한 종류의 풀을 True, 다른 종류의 풀을 False로 설정하고 SCC를 사용합니다. 입력에서 10개의 목초지가 주어지고 5마리의 소의 입력이 다음과 같다고 생각해봅시다. S 1 2 S 3 4 S 5 6 S 7 8 S 9 10 이 경우는 32가지가 정답인 것을 알 수 있습니다. 1 2 ..

문제 https://www.acmicpc.net/problem/5009 알고리즘 2-SAT, 이분탐색 풀이 우리가 결정해야 할 것은 아이들의 호감리스트를 반영한 아이들의 반 배정입니다. 언뜻 보면 선생님이 3명이여서 아이들이 결정해야할 선생님이 세 사람 같아 보이지만 실제론 두 사람입니다. 이유는 작년에 담당했던 선생님은 선택사항이 아니기 때문입니다. 문제 조건중 "반에 속하는 모든 학생은 학생들이 좋아하는 순서에서 상위 T위 안에 있어야 한다."는 달리 말해서 T위를 초과하는 학생과는 다른 반이 되어야 함을 의미합니다. 다른 반으로 배정하기 위해선 두 학생의 이전 선생님이 누구인지 알아야 하며, 이에 따라 반배정을 진행해주면 됩니다. 각 선생님 번호가 0 , 1 , 2라고 할 때, T(x)는 이전 선생..

문제 https://www.acmicpc.net/problem/16915 알고리즘 2-SAT 풀이 풀면서 이 문제와 굉장히 유사하다고 느꼈습니다. 각 방마다 스위치가 두 개가 있고, 방의 상태에 따라 다음과 같은 선택을 할 수 있습니다. 각 방마다 연결되어있는 스위치를 A, B라고 하겠습니다. 1. 만약 방의 초기상태가 켜져 있다면, A와 B 둘 다 눌러서 켜진 상태를 유지하거나 A와 B둘다 누르지 않습니다. 2. 방의 초기상태가 꺼진 상태라면, A를 눌렀을 땐 B를 누르지 않고 B를 눌렀을 땐 A를 누르지 않아 켜지도록 합니다. 위 두 문장은 And or And 관계로 표현가능하며 2-CNF형태를 만족시키도록 전개해주면 문제를 풀 수 있습니다. 코드 #include #define rep(i,n) for..

문제 https://www.acmicpc.net/problem/15675 알고리즘 2-SAT 풀이 강산이가 보석을 훔치기 위해선 행 또는 열에 한 번만 입장을 해야 합니다. 관장 택희가 보석이 도난당할 시, 즉시 경비원을 출동시키기 때문에 두 번 다시 입장이 불가능하기 때문입니다. 훔치는 과정에서 위치추적기를 얻을 시에는 언젠가는 다시 한번 방문을 해서 위치추적기를 떼어 놓아야만 합니다. 즉 박물관 좌표 $y$행,$x$열에 대하여 보석이 위치한 곳에는 $(T(y)\cap F(x))\cup (F(y)\cap T(x))$ 를 만족하며 추적기가 위치한 곳에 대해서는 $(T(y)\cap T(x))\cup (F(y)\cap F(x))$ 를 만족합니다. $T()$는 해당 행 또는 열을 방문한다는 의미이며 $F()$..

문제 https://www.acmicpc.net/problem/3648 알고리즘 2-SAT 풀이 문제에서 2-SAT의 느낌을 물씬 풍기는 문장이 몇 있습니다. '적어도 하나'라는 문장은 OR을 연상케 하고 OR은 2-CNF에서 하나의 절을 구성합니다. 그리고 한 참가자에 대해 두 가지 선택을 할 수 있다는 점도 True와 False로 연관 지을 수 있으니 2-SAT으로 문제를 접근합시다. 심사위원의 의심 없이 다음라운드를 구성할 수 있다면 하나의 참가자에 대해 모순이 되는 경우가 없다는 의미와 같습니다. 즉, 각 정점의 True와 False의 $sccid$가 일치해서는 안됩니다. 상근이가 진출하는 경우는 그래프상에서 상근이의 False 정점이 True 정점보다 위상정렬상 빠른지 확인하면 됩니다. 이전 문..

문제 https://www.acmicpc.net/problem/11281 알고리즘 2-SAT 풀이 이 문제에서 실제 해까지 찾아서 출력하는 문제입니다. SCC 이후 하나의 간선을 구성하는 두 정점을 살펴봅시다. 앞서 살펴본 바와 같이 u->v를 만족하기 위해선 not u 일 땐 v가 무엇이 와도 상관이 없으나 True u 일 땐 2-CNF에서의 절을 만족하기 위해 v가 True임이 강제됩니다. 즉 우리는 위상 정렬상 빠른 쪽에 위치한 정점을 False로 평가하는 것이 True로 평가하는 것에 비해 항상 이득임을 알 수 있습니다. 코드 #include #define rep(i,n) for(int i=0;i u >> v; OR(u, v); } discovered = sccid = vector(N

문제 https://www.acmicpc.net/problem/11280 알고리즘 2-SAT 풀이 SCC알고리즘을 활용하여 2-SAT을 모델링하는 문제입니다. True나 False를 판단해야 하는 하나의 변수에 대해 이미 True나 False를 정해주고 모순이 생기는지만 확인하는 문제입니다. 각 절에 대해 두 개의 or 관계가 주어지면 우리가 얻을 수 있는 정보는 다음과 같습니다. A or B가 주어졌을 때 False A 라면 True B 여야 하고, False B 라면 True A 여야만 합니다. 두 개의 정보에 대해 우리는 간선으로 표현할 수 있으며, 만약 하나의 정점 C에 대해 False C와 True C가 동일한 컴포넌트로 묶인다면 이는 모순임을 나타냅니다. 변수는 1부터 시작하므로 크기를 할당할..