알고리즘/알고리즘 공부 내용 정리
백준 BOJ 2-SAT 알고리즘 심화 문제 풀이
restudy
2022. 11. 27. 23:13
반응형
백준 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";
}
반응형