BOJ 1739 - 도로 정비하기

티어: D5 (체감 D5)

알고리즘: 2-SAT

---

여기서는 가로 도로를 행, 세로 도로를 열로 표기한다.

어떤 버스가 (a,b)에서 (c,d)로 갈려면 다음 2가지 중 하나를 이용해야 한다. (도로를 최대 2개밖에 이용하지 못하기 때문)

1. a행, d열을 이용한다.

2. c행, b열을 이용한다.

일단 a≠c, b≠d라고 가정하고 예제 1의 테스트케이스 1을 보자.

 

 

위 그림은 테스트케이스 1번에서 (1,1)에서 (6,6)으로 가는 버스를 나타낸 것이다.

빨간색 경로는 1행과 6열을 이용해서 (1,1)에서 (6,6)으로 간다.

파란색 경로는 1열과 6행을 이용해서 (1,1)에서 (6,6)으로 간다.

 

위를 통해 (a,b)에서 (c,d)로 갈려면 a행, d열을 이용하거나 c행, b열을 이용해야 함을 알 수 있다.

그런데 a=c이거나 b=d라면 어떨까?

위 상황에서 파란색 경로는 (1,1)에서 (6,1), 빨간색 경로는 (1,6)에서 (6,6)으로 간다.

이때 두 경로는 각각 1행과 6행을 이용해야하며, 열은 관련이 없다.

이 경우는 b=d인 경우이고 이때는 a,c가 무관함을 알 수 있다.

같은 방법으로 a=c일때는 b,d가 무관하다.

 

여기까지 이해했으면 2-sat을 짤 수 있다.

먼저 (a,b)에서 (c,d)로 갈려면 "a행, d열을 이용하거나 c행, b열을 이용"해야 하므로 다음과 같은 식을 세울 수 있다.

(a∧d)∨(c∧b)

위 식은 2-sat 형태(CNF)와 and, or이 반대이므로 위 식을 CNF로 바꿔줘야 한다.

위 식을 다시 생각해보면,

(a∨c)∧(b∨d)∧(a∨b)∧(c∨d)

임을 알 수 있다.

이 상태로 바로 2-sat을 돌리면 안되고, 2가지를 더 고려해야 한다.

 

1.a=c 또는 b=d(a=c && b=d 포함)

이 경우는 그냥 위에서 말한것처럼 무관한 행 또는 열은 제외하고 간선을 추가하면 된다.

 

2.방향

(1,1)에서 (6,6)에서 가는것과 (6,6)에서 (1,1)로 가는것은 다르다. 따라서 왼쪽 또는 위 방향에서는 not을 붙여 CNF를 만들면 된다.

 

코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
using namespace std;
ll t;
ll n, m, k, M;
ll scc[4040], num[4040], cnt, scnt;
bool finished[4040];
stack<ll> s;
inline ll conv(ll x){ return x>M ? x-M : x+M; }
vector<ll> adj[4040];
ll dfs(ll x){
    ll chk = ++cnt;
    num[x] = chk;
    s.push(x);
    for(auto next : adj[x]){
        if(!num[next])chk = min(chk, dfs(next));
        else if(!finished[next])chk = min(chk, num[next]);
    }
    if(chk==num[x]){
        scnt++;
        while(1){
            ll cur = s.top();
            s.pop();
            finished[cur]=1;
            scc[cur]=scnt;
            if(cur==x)break;
        }
    }
    return chk;
}
int main(){
    fast;
    cin>>t;
    while(t--){
        memset(scc,0,sizeof(scc));
        memset(num,0,sizeof(num));
        memset(finished,0,sizeof(finished));
        for(int i = 0 ; i < 4040 ; i++)adj[i].clear();
        cnt=scnt=0;
        cin>>n>>m>>k;
        M = n+m;
        for(int i = 1 ; i <= k ; i++){
            ll a,b,c,d; cin>>a>>b>>c>>d;
            if(a==c and b==d)continue;
            ll A=a,B=n+b,C=c,D=n+d;
            if(a>c)B=conv(B), D=conv(D); //방향이 반대면 NOT
            if(b>d)A=conv(A), C=conv(C);
            if(a!=c and b!=d){
                adj[conv(A)].push_back(B);
                adj[conv(B)].push_back(A);
                adj[conv(C)].push_back(D);
                adj[conv(D)].push_back(C);
            }
            if(b!=d){
                adj[conv(A)].push_back(C);
                adj[conv(C)].push_back(A);
            }
            if(a!=c){
                adj[conv(B)].push_back(D);
                adj[conv(D)].push_back(B);
            }
        }
        for(int i = 1 ; i <= M*2 ; i++)if(!num[i])dfs(i);
        bool f=1;
        for(int i = 1 ; i <= M ; i++){
            if(scc[i]==scc[conv(i)])f=0;
        }
        cout<<(f ? "Yes" : "No")<<"\n";
    }
}

지금까지 푼 D5중에 가장 빨리 풀었다(30분). 근데 문제는 푼 D5가 3개뿐이라는것.(풀면 다 P1로 내려감 ㅠ)