백준 BOJ 2-SAT 알고리즘 심화 문제 풀이

백준 BOJ 1739번 : 도로 정비하기

문제 난이도 : Platinum I

알고리즘 분류 : 2-SAT

 

어떤 가로 도로에 대해서 왼쪽 일방 통행의 경우 T, 오른쪽이면 F로 임의로 두자.

마찬가지로 세로 도로에 대해서도 위 방향은 T, 아래 방향을 F로 두자.

방향은 푸는 사람이 정의하면 된다. 명제 연결할 때만 제대로 연결하면 관계없다.

이제 어떤 점에서 다른 점으로의 이동에 대해, 두 가지 경로가 있으므로, 두 경로에 대해 (A and B) or (C and D)꼴이 나온다.

이것을 식을 풀어서 (나는 분배 법칙으로 풀었다.) (E or F) and (G or H) 꼴로 바꾼 뒤 2-SAT를 적용해주면 된다.

 

이 문제는 2-SAT에 다른 알고리즘이 접목된 문제도 아닌데 난이도가 Platinum I이다.

왜냐하면 나눠야 할 조건 분기가 너무 많고, 동시에 각각 연결해야 할 명제의 개수도 매우 많다.

 

아래에 모든 경우의 수를 정리해두었으니 그림을 참고하면 좋을 것이다.

 

 

 

↓ 풀이 코드는 여기에 있다.

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;

stack<int> s;
vector<bool> ch;

int y(int x) {
    if(x < 0) return (-x)*2 - 2;
    else return x*2 - 1;
}

int n(int x) {
    x = y(x);

    if(x % 2 == 0) return x + 1;
    else return x - 1;
}

int dfs(int x) {
    nnum[x] = ++ncnt;
    s.push(x);

    int tmp = nnum[x];

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(nnum[y] == 0) tmp = min(tmp, dfs(y));
        else if(!ch[y]) tmp = min(tmp, nnum[y]);
    }

    if(tmp == nnum[x]) {
        vector<int> v;
        ccnt++;

        while(true) {
            int y = s.top();
            s.pop();

            v.push_back(y);

            ch[y] = true;
            cnum[y] = ccnt;

            if(y == x) break;
        }

        sort(v.begin(), v.end());

        scc.push_back(v);
    }

    return tmp;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;

    while(T--) {
        int R, C, K; cin >> R >> C >> K;

        int N = R + C;

        adj.clear(); adj.resize(N*2);

        while(K--) {
            int bx, by, ex, ey; cin >> bx >> by >> ex >> ey;

            if(bx == ex && by < ey) adj[y(bx)].push_back(n(bx));
            else if(bx == ex && by > ey) adj[n(bx)].push_back(y(bx));
            else if(bx > ex && by == ey) adj[n(R+by)].push_back(y(R+by));
            else if(bx < ex && by == ey) adj[y(R+by)].push_back(n(R+by));
            else if(bx < ex && by < ey) {
                adj[y(bx)].push_back(n(ex));
                adj[y(ex)].push_back(n(bx));
                adj[y(bx)].push_back(n(R+by));
                adj[y(R+by)].push_back(n(bx));
                adj[y(ex)].push_back(n(R+ey));
                adj[y(R+ey)].push_back(n(ex));
                adj[y(R+ey)].push_back(n(R+by));
                adj[y(R+by)].push_back(n(R+ey));
            }
            else if(bx < ex && by > ey) {
                adj[n(bx)].push_back(y(ex));
                adj[n(ex)].push_back(y(bx));
                adj[n(bx)].push_back(n(R+by));
                adj[y(R+by)].push_back(y(bx));
                adj[n(ex)].push_back(n(R+ey));
                adj[y(R+ey)].push_back(y(ex));
                adj[y(R+ey)].push_back(n(R+by));
                adj[y(R+by)].push_back(n(R+ey));
            }
            else if(bx > ex && by < ey) {
                adj[y(bx)].push_back(n(ex));
                adj[y(ex)].push_back(n(bx));
                adj[y(bx)].push_back(y(R+by));
                adj[n(R+by)].push_back(n(bx));
                adj[y(ex)].push_back(y(R+ey));
                adj[n(R+ey)].push_back(n(ex));
                adj[n(R+ey)].push_back(y(R+by));
                adj[n(R+by)].push_back(y(R+ey));
            }
            else if(bx > ex && by > ey) {
                adj[n(bx)].push_back(y(ex));
                adj[n(ex)].push_back(y(bx));
                adj[n(bx)].push_back(y(R+by));
                adj[n(R+by)].push_back(y(bx));
                adj[n(ex)].push_back(y(R+ey));
                adj[n(R+ey)].push_back(y(ex));
                adj[n(R+ey)].push_back(y(R+by));
                adj[n(R+by)].push_back(y(R+ey));
            }
        }

        nnum.clear(); nnum.resize(N*2);
        cnum.clear(); cnum.resize(N*2);
        ch.clear();   ch.resize(N*2);

        scc.clear();
        ncnt = ccnt = 0;

        for(int i=0; i<N*2; i++)
            if(nnum[i] == 0) dfs(i);

        bool check = true;

        for(int i=0; i<N; i++) {
            if(cnum[i*2] == cnum[i*2 + 1]) {
                check = false;
                break;
            }
        }

        if(check) cout << "Yes\n";
        else cout << "No\n";
    }
}

 

 

백준 BOJ 5009번 : 유치원

문제 난이도 : Platinum I

알고리즘 분류 : 2-SAT, 이분 탐색

 

2-SAT에 이분 탐색을 결합한 문제이다.

큰 틀에서는 적절한 T를 찾기 위해 0 ~ N-1 사이에서 이분 탐색을 하며 T를 찾아주면 된다.

 

2-SAT 문제로 치환하기 위해, 특정 번호 i가 0반에 속하는지의 여부, 1반에 속하는지의 여부, 2반에 속하는지의 여부를 각각 bool 변수로 생각해서 3N개의 변수를 만들어주고, 명제 관계만 잘 연결해주면 된다.

예를 들어 T를 기준으로 등수가 더 낮은 번호와는 같은 반이 되면 안 되므로, "i가 x반이면 → j는 x반이 아니다", 동시에 "j가 x반이면 → i는 x반이 아니다" 이런 식으로 명제들을 연결해줄 수 있다.

 

모든 명제 조건을 다 설명하기엔 길기 때문에 풀이 코드를 참고하면 도움이 될 것이다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;

stack<int> s;
vector<bool> ch;

int y(int x) {
    if(x < 0) return (-x)*2 - 2;
    else return x*2 - 1;
}

int n(int x) {
    x = y(x);

    if(x % 2 == 0) return x + 1;
    else return x - 1;
}

int dfs(int x) {
    nnum[x] = ++ncnt;
    s.push(x);

    int tmp = nnum[x];

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(nnum[y] == 0) tmp = min(tmp, dfs(y));
        else if(!ch[y]) tmp = min(tmp, nnum[y]);
    }

    if(tmp == nnum[x]) {
        vector<int> v;
        ccnt++;

        while(true) {
            int y = s.top();
            s.pop();

            v.push_back(y);

            ch[y] = true;
            cnum[y] = ccnt;

            if(y == x) break;
        }

        sort(v.begin(), v.end());

        scc.push_back(v);
    }

    return tmp;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<int> v(N+1);
    vector<vector<int>> u(N+1, vector<int>(N));

    for(int i=1; i<=N; i++) {
        cin >> v[i];

        for(int j=1; j<=N-1; j++) cin >> u[i][j];
    }

    int l = 0, r = N-1, ans = N-1;
    int M = N * 3;

    while(l <= r) {
        int m = (l + r) / 2;

        adj.clear(); adj.resize(M*2);

        for(int i=1; i<=N; i++) {
            adj[y(v[i]*N + i)].push_back(n(v[i]*N + i));

            int a = ((v[i] + 1) % 3)*N + i;
            int b = ((v[i] + 2) % 3)*N + i;

            adj[n(a)].push_back(y(b));
            adj[n(b)].push_back(y(a));

            for(int j=m+1; j<=N-1; j++)
                for(int k=0; k<3; k++) {
                    if(k == v[i]) continue;

                    adj[y(k*N + i)].push_back(n(k*N + u[i][j]));
                    adj[y(k*N + u[i][j])].push_back(n(k*N + i));
                }
        }

        nnum.clear(); nnum.resize(M*2);
        cnum.clear(); cnum.resize(M*2);
        ch.clear();   ch.resize(M*2);

        scc.clear();
        ncnt = ccnt = 0;

        for(int i=0; i<M*2; i++)
            if(nnum[i] == 0) dfs(i);

        bool check = true;

        for(int i=0; i<M; i++) {
            if(cnum[i*2] == cnum[i*2 + 1]) {
                check = false;
                break;
            }
        }

        if(check) {
            ans = min(ans, m);
            r = m - 1;
        }
        else l = m + 1;
    }

    cout << ans << "\n";
}

 

 

백준 BOJ 2519번 : 막대기

문제 난이도 : Diamond V

알고리즘 분류 : 2-SAT, 선분 교차 판정

 

2-SAT 문제에 선분 교차 판정이 접목된 문제이다.

구현이 쉽지 않은 두 알고리즘이 모두 사용되기 때문에 다른 2-SAT 문제에 비해 구현량이 매우 많다.

 

다만 두 가지를 구현할 줄만 알면 간단한 명제 식 몇 개만 풀면 문제가 쉽게 풀리므로, 곧 투표에 의해 Platinum으로 난이도가 하향될 것 같기도 하다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { int x, y; };

bool operator== (s a, s b) {
    if(a.x == b.x && a.y == b.y) return true;
    else return false;
}
bool operator>= (s a, s b) {
    if(a.x > b.x || (a.x == b.x && a.y >= b.y)) return true;
    else return false;
}
bool operator<= (s a, s b) {
    if(a.x < b.x || (a.x == b.x && a.y <= b.y)) return true;
    else return false;
}
bool operator> (s a, s b) {
    if(a.x > b.x || (a.x == b.x && a.y > b.y)) return true;
    else return false;
}
bool operator< (s a, s b) {
    if(a.x < b.x || (a.x == b.x && a.y < b.y)) return true;
    else return false;
}

int ccw(s a, s b, s c) {
    int val = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);

    if(val == 0) return 0;
    else if(val > 0) return 1;
    else if(val < 0) return -1;
}

bool cross, overlap;
double cx, cy;

void coor(s a, s b, s c, s d) {
    double X = (a.x * b.y - a.y * b.x) * (c.x - d.x) - (a.x - b.x) * (c.x * d.y - c.y * d.x);
    double Y = (a.x * b.y - a.y * b.x) * (c.y - d.y) - (a.y - b.y) * (c.x * d.y - c.y * d.x);
    double div = (a.x - b.x) * (c.y - d.y) - (a.y - b.y) * (c.x - d.x);

    if(div == 0) {
        if(b == c && a <= c) cx = b.x, cy = b.y, overlap = false;
        else if(a == d && c <= a) cx = a.x, cy = a.y, overlap = false;
        else overlap = true;
    }
    else cx = X / div, cy = Y / div, overlap = false;
}

void inter(s a, s b, s c, s d) {
    int val1 = ccw(a, b, c) * ccw(a, b, d);
    int val2 = ccw(c, d, a) * ccw(c, d, b);

    if(val1 == 0 && val2 == 0) {
        if(a > b) swap(a, b);
        if(c > d) swap(c, d);

        if(a <= d && b >= c) {
            cross = true;
            coor(a, b, c, d);
        }
        else cross = false;
    }
    else {
        if(val1 <= 0 && val2 <= 0) {
            cross = true;
            coor(a, b, c, d);
        }
        else cross = false;
    }
}

vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;

stack<int> st;
vector<bool> ch;

int dfs(int x) {
    nnum[x] = ++ncnt;
    st.push(x);

    int tmp = nnum[x];

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(nnum[y] == 0) tmp = min(tmp, dfs(y));
        else if(!ch[y]) tmp = min(tmp, nnum[y]);
    }

    if(tmp == nnum[x]) {
        vector<int> v;
        ccnt++;

        while(true) {
            int y = st.top();
            st.pop();

            v.push_back(y);

            ch[y] = true;
            cnum[y] = ccnt;

            if(y == x) break;
        }

        sort(v.begin(), v.end());

        scc.push_back(v);
    }

    return tmp;
}

int cvt(int x) {
    if(x < 0) return (-x)*2 - 2;
    else return x*2 - 1;
}

int cvtn(int x) {
    x = cvt(x);

    if(x % 2 == 0) return x + 1;
    else return x - 1;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    N *= 3;

    vector<vector<s>> v(N+1, vector<s>(2));

    for(int i=1; i<=N; i++)
        cin >> v[i][0].x >> v[i][0].y >> v[i][1].x >> v[i][1].y;

    adj.resize(N*2);

    for(int i=1; i<=N; i+=3) {
        adj[cvt(i)].push_back(cvtn(i+1));
        adj[cvt(i)].push_back(cvtn(i+2));

        adj[cvt(i+1)].push_back(cvtn(i));
        adj[cvt(i+1)].push_back(cvtn(i+2));

        adj[cvt(i+2)].push_back(cvtn(i));
        adj[cvt(i+2)].push_back(cvtn(i+1));
    }

    for(int i=1; i<=N; i++)
        for(int j=i+1; j<=N; j++) {
            inter(v[i][0], v[i][1], v[j][0], v[j][1]);

            if(cross) {
                adj[cvtn(i)].push_back(cvt(j));
                adj[cvtn(j)].push_back(cvt(i));
            }
        }

    nnum.resize(N*2);
    cnum.resize(N*2);
    ch.resize(N*2);

    for(int i=0; i<N*2; i++)
        if(nnum[i] == 0) dfs(i);

    bool check = true;

    for(int i=0; i<N; i++) {
        if(cnum[i*2] == cnum[i*2 + 1]) {
            check = false;
            break;
        }
    }

    if(!check) {
        cout << -1 << "\n";
        return 0;
    }

    vector<pair<int, int>> p(N*2);
    for(int i=0; i<N*2; i++) p[i] = {cnum[i], i};

    sort(p.begin(), p.end(), greater<pair<int, int>>());

    vector<int> tf(N*2, -1);

    for(int i=0; i<N*2; i++) {
        int x = p[i].second;

        if(tf[x/2] == -1) {
            if(x % 2 == 1) tf[x/2] = 0;
            else tf[x/2] = 1;
        }
    }

    vector<int> u;

    for(int i=0; i<N; i++)
        if(tf[i]) u.push_back(i+1);

    cout << u.size() << "\n";

    for(int i=0; i<u.size(); i++) cout << u[i] << " ";
    cout << "\n";
}

 

 

백준 BOJ 25456번 : 궁금한 시프트

문제 난이도 : Platinum I

알고리즘 분류 : FFT

 

이 문제는 2-SAT 문제가 아니고 FFT 문제인데 적을 곳이 없기도 하고 설명할 내용도 거의 없어서 여기에 끼워넣는다.

백준 BOJ 1067번 : 이동 문제와 거의 구조가 비슷하고, 풀이 코드 또한 거의 유사하다.

따라서 원리만 그대로 가져다가 풀어주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

const double PI = acos(-1);
typedef complex<double> cpx;

void FFT(vector<cpx> &v, bool inv) {
    int S = v.size();

    for(int i=1, j=0; i<S; i++) {
        int bit = S/2;

        while(j >= bit) {
            j -= bit;
            bit /= 2;
        }
        j += bit;

        if(i < j) swap(v[i], v[j]);
    }

    for(int k=1; k<S; k*=2) {
        double angle = (inv ? PI/k : -PI/k);
        cpx w(cos(angle), sin(angle));

        for(int i=0; i<S; i+=k*2) {
            cpx z(1, 0);

            for(int j=0; j<k; j++) {
                cpx even = v[i+j];
                cpx odd = v[i+j+k];

                v[i+j] = even + z*odd;
                v[i+j+k] = even - z*odd;

                z *= w;
            }
        }
    }

    if(inv)
        for(int i=0; i<S; i++) v[i] /= S;
}

vector<int> mul(vector<int> &v, vector<int> &u) {
    vector<cpx> vc(v.begin(), v.end());
    vector<cpx> uc(u.begin(), u.end());

    int S = 2;
    while(S < v.size() + u.size()) S *= 2;

    vc.resize(S); FFT(vc, false);
    uc.resize(S); FFT(uc, false);

    for(int i=0; i<S; i++) vc[i] *= uc[i];
    FFT(vc, true);

    vector<int> w(S);
    for(int i=0; i<S; i++) w[i] = round(vc[i].real());

    return w;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    string a, b; cin >> a >> b;

    int N = a.length();

    vector<int> v(N*2), u(N);
    
    for(int i=0; i<N; i++) v[i] = v[i+N] = a[i] - '0';
    for(int i=0; i<N; i++) u[N-1-i] = b[i] - '0';

    vector<int> w = mul(v, u);

    int ans = 0;
    for(int i=0; i<w.size(); i++) ans = max(ans, w[i]);

    cout << ans << "\n";
}