📝 문제 정보#
🧐 관찰 및 접근#
- $(1, 1) \rightarrow (6, 6)$으로 가기 위해선 어때야 하지?
- $r_1, c_6$이 오른쪽 / 아래이거나, $c_1, r_6$이 아래 / 오른쪽이거나..
- 오른쪽 / 아래를 참, 왼쪽/위를 거짓이라고 생각하면,
- $(r_1 \land c_6) \lor (r_6 \land c_1)$ 같은 느낌인가?
- 이걸 어떻게 잘 하면 2-sat으로 바꿀 수 있을것같은데..
- $r6$이 아니라면, $r1, c6$이 참이어야하고, 이런 느낌으로 되는것같다.
- $(\neg r_6 \rightarrow r_1) \land (\neg r_6 \rightarrow c_6)$
- 이런걸 4개에 대해서 하면 될거같은데?
- $(r_1, c_1) \rightarrow (r_2, c_2)$ 라고 해보자.
- 일단 $r_1 < r_2, c_1 < c_2$라고 하자.
- $(\neg r_1 \rightarrow r_2) \land (\neg r_1 \rightarrow c_1)$
- $(\neg c_2 \rightarrow r_2) \land (\neg c_2 \rightarrow c_1)$
- $(\neg r_2 \rightarrow r_1) \land (\neg r_2 \rightarrow c_2)$
- $(\neg c_1 \rightarrow r_1) \land (\neg c_1 \rightarrow c_2)$
- 이렇게 할 수 있을 것 같다.
- 그러면 $r_1 > r_2, c_1 > c_2$라면?
- 똑같이 $r_1, c_2$의 경로를 이용하거나, $r_2, c_1$의 경로를 이용해야하는건 같다.
- 그런데 왼쪽이라서 참이어야 하는게 아니라 목적지가 거짓이어야 한다.
- $(\neg r_1 \land \neg c_2) \lor (\neg r_2 \land \neg c_1)$ 처럼 되어야할 것 같다.
- 아하, 대소관계가 바뀌면 이게 낫으로 바뀐다. 이걸 이용해서 더 쉽게 구현이 될라나?
- 일단 $r_1 < r_2, c_1 < c_2$라고 하자.
- 구현 실수하지 않게 조심하자.
💻 풀이#
- 코드 (C++):
void solve(){
int N, M, K; cin >> N >> M >> K;
DirectedGraph tsat((N+M)*2);
rep(i, 0, K){
int r1, c1, r2, c2;
cin >> r1 >> c1 >> r2 >> c2;
r1--; c1--; r2--; c2--;
r1 *= 2; r2 *= 2;
c1 = (c1 + N) * 2;
c2 = (c2 + N) * 2;
if(r1 == r2 && c1 == c2) continue;
if(r1 == r2){
if(c1 < c2) tsat.add_edge(r1^1, r1);
else tsat.add_edge(r1, r1^1);
continue;
}
if(c1 == c2){
if(r1 < r2) tsat.add_edge(c1^1, c1);
else tsat.add_edge(c1, c1^1);
continue;
}
if(c1 > c2) r1^=1, r2^=1;
if(r1 > r2) c1^=1, c2^=1;
tsat.add_edge(c1^1, r1);
tsat.add_edge(c1^1, c2);
tsat.add_edge(r2^1, r1);
tsat.add_edge(r2^1, c2);
tsat.add_edge(r1^1, r2);
tsat.add_edge(r1^1, c1);
tsat.add_edge(c2^1, r2);
tsat.add_edge(c2^1, c1);
}
cout << (tsat.is2SAT() ? "Yes\n" : "No\n");
}