SCC, 2-SAT 문제 유형 정리

1. SCC문제

1) SCC 구성하기

백준 2150번 Strongly Connected Component

백준 11097번 도시 계획 : 최소 간선으로 scc를 만족하는 그래프 만들기

백준 25488번 토큰 : [★★★] scc별 빨간 카드, 파란 카드에 적힌 숫자의 수 비교하기

백준 1506번 경찰서 : [★★] scc마다 최소 비용만 찾아서 다 더하기

 

2) a에서 b까지 가장 많은 정점을 방문하는 경로

백준 1471번 사탕 돌리기 : [★★★] 모든 정점의 진출차수가 1인 그래프

백준 19649번 미담 전하기 : 직접 전파자를 포함하지 않아야 하는 조건 처리가 까다로움

백준 2152번 여행 계획 세우기 : [★★★] 같은 컴포넌트의 요소들은 크기만 알면 방문한 셈 칠 수 있음

백준 4013번 ATM : [★★★★★] dag에서 dfs로 scc뽑은 다음, scc로 만들어진 dag에서 또 dfs 돌려서 최대치 얻기(dp)

백준 14249번 점프 점프 2 : [★★★★] ATM과 똑같은 문제

 

3) SCC간 DAG의 연결 관계

백준 3977번 축구 전술 : SCC로 구성된 DAG에서 진입차수가 0인 컴포넌트의 유일성을 확인

백준 6543번 그래프의 싱크 : [★★] DAG에서 진출 간선이 없는 SCC의 컴포넌트를 모두 출력

백준 20504번 I번은 쉬운 문제 : [★★★] 진입차수가 0인 scc에 포함된 테스트케이스를 확인

 

2. 2-SAT 문제

1) 가부 판정

백준 11280번 2-SAT - 3 : 2-SAT 구성이 가능한지 확인

백준 2207번 가위바위보 : 둘 중 하나만 내면 되기 때문에 2-SAT

2) 가능한 상태 탐색

백준 11281번 2-SAT - 4 : 2-SAT 구성이 가능한 논리 값

백준 2416번 문 : 스위치들의 조작 여부로 2-SAT

 

3) 변형 CNF

백준 15675번 괴도 강산 : [★★] 위치 추적기와 보석으로 만들어지는 clause가 서로 다른 형태를 띠므로 각각 유도되는 간선이 다름

백준 16915번 호텔 관리 : [★★★] 초기 상태가 지정되어 있어 유도되는 간선이 일반적이지 않고, 두 개의 scc에 2-sat 확인해야 함

백준 32182번 POEM : [★] 논리 간선 유도하는 방법이 매우 특이함(여러 값에 대한 xor 성질 이용)

백준 1739번 도로 정비하기 : [★★] 역시 간선 유도가 매우 특이함(논리합과 논리곱의 분배법칙, (a ∨ a) = True)

백준 155668번 개구리 3 : 1개 또는 2개 중 하나의 연꽃에 앉으려고 하는 개구리들을 배치하는 문제. 간선 처리가 복잡함

백준 5009번 유치원 : [★★★★] 3-sat인 척 하는 매개변수탐색이 가미된 맛있는 2-sat문제

백준 19703번 실험 : 땅따먹기가 뽑아주신 미친 개어려운 2-sat, 뭐 at-most-one? Sequential Encoding, Sinz's encoding을 써야 한다함 뭐라하는지 하나도 알아먹을 수가 없음. 이해 하나도 못하고 그냥 테크닉만 따라해서 겨우 풀었음 뭐 이딴 문제가 다있냐!