백준16367 TV Show Game

작성일 | In

문제 링크

  • http://icpc.me/15367

문제 출처

  • 2018 서울 리저널 K번

사용 알고리즘

  • 2-SAT

풀이

각 램프에 대해, R이면 true, B이면 false라고 합시다. 갑자기 2-SAT을 쓰고싶어집니다.

조건 A, B, C 중에서 2개 이상 만족한다는 것을 2-CNF로 나타내는 것에서 막힐 수 있는데, (A or B) and (B or C) and (C or A)로 처리할 수 있습니다.
(A or B) and (B or C) and (C or A)라는 식을 찾아냈으면 단순히 2-SAT을 돌려서 정답을 역추적해주면 됩니다.

CNF를 추가하는 것을 구현하는 것이 귀찮을 수 있는데, 아래 코드처럼 하면 실수하지 않고 깔끔하게 처리할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline int inv(int x){
	if(x > n) return x - n;
	return x + n;
}

void addCNF(int s, int e){
	if(s < 0) s = inv(-s);
	if(e < 0) e = inv(-e);
	addEdge(inv(s), e);
	addEdge(inv(e), s);
}

for(int i=0; i<m; i++){
		int a[4]; char b[4];
		for(int j=0; j<3; j++) cin >> a[j] >> b[j];
		a[3] = a[0], b[3] = b[0];
		for(int j=0; j<4; j++) if(b[j] == 'B') a[j] *= -1;
		for(int j=0; j<3; j++){
			addCNF(a[j], a[j+1]);
		}
	}