2차원 배열에 전구가 박혀있다.
전구는 행에 한개, 열에 한개 총 두 개의 스위치에 연결되있다.
스위치에 연결되있는 전구들은 상태를 toggle시킨다.
전구와 연결된 스위치와 전구의 상태가 주어질 때 모든 전구를 킬 수있는 스위치를 구하는 문제이다.
2017 SCPC 1차 예선 3번 문제였다.
이 문제를 풀어보겠다고 별짓을 다했던 기억이 남는다.
처음에는 greedy하게 접근해보기도 하고 그래프로 풀어보려고도 했는데
다 실패해서 마지막으로 종만북을 보면서 적용시킬게 있나 찾아보다가
2-sat개념을 보고 적용시키니 성공할 느낌이 왔었다!
하지만 그때 2-sat 문제를 풀어보기는 커녕 개념조차 처음 본거였고 새벽3시가 넘어서
주워온 코드로 대충 때려박고 WA가 뜨길래 바로 잤다.
앞서 말했듯이 이 문제는 2-sat으로 풀 수있다.
전구와 연결된 행쪽 스위치를 $row$, 열쪽 스위치를 $col$이라 하면
1. 전구가 켜져있는 상태
($row$ && $col$) || ($!row$ && $!col$)
이것을 2-cnf로 변환시키면 ($row$ || $!col$) && ($!row$ || $col$)
2. 전구가 꺼져있는 상태
($row$ && $!col$) || ($!row$ && $col$)
이것을 2-cnf로 변환시키면 ($row$ || $col$) && ($!row$ || $!col$)
간단히 말하면 꺼져있는 상태는 xor, 켜져있는 상태는 and연산으로 스위치가 작동해야된다.
위의 두 2-cnf식도 그당시에 구하기도했었지만 구현을 못했다 ㅠㅠ
스위치들끼리 2-cnf식에 의해 연결 시킨 이후에는 scc가 모순이 없는지 판단한 후에 없다면
https://www.acmicpc.net/problem/11281에서 처럼 처리해주면 된다.
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
#define MAX 55555
int N, M;
int visit[MAX];
bool finish[MAX];
int scc[MAX];
int save[MAX][3];
int rr[101][101], cc[101][101];
int cnt, scc_cnt, idx;
stack<int> stk;
vector<vector<int>> adj;
vector<vector<pair<int, int>>>::iterator i;
int getRow(int n, int r) {
if (rr[n][r] == -1) {
save[idx][0] = false;
save[idx][1] = n, save[idx][2] = r;
rr[n][r] = idx++;
}
return rr[n][r];
}
int getCol(int m, int c) {
if (cc[m][c] == -1) {
save[idx][0] = true;
save[idx][1] = m, save[idx][2] = c;
cc[m][c] = idx++;
}
return cc[m][c];
}
int dfs(int here) {
int ret = visit[here] = ++cnt;
stk.push(here);
for (int next : adj[here]) {
if (!visit[next]) ret = min(ret, dfs(next));
else if (!finish[next]) ret = min(ret, visit[next]);
}
if (ret == visit[here]) {
++scc_cnt;
while (1) {
int t = stk.top();
stk.pop();
finish[t] = true;
scc[t] = scc_cnt;
if (t == here) break;
}
}
return ret;
}
int main() {
int T;
scanf("%d", &T);
for (int t = 1;t <= T;t++) {
cnt = scc_cnt = idx = 0;
memset(rr, -1, sizeof rr);
memset(cc, -1, sizeof cc);
memset(save, 0, sizeof save);
memset(visit, 0, sizeof visit);
memset(finish, 0, sizeof finish);
memset(scc, 0, sizeof scc);
adj = vector<vector<int>>(MAX);
scanf("%d%d", &N, &M);
for (int n = 0;n < N;n++) {
for (int m = 0;m < M;m++) {
int light, r, c;
scanf("%d%d%d", &light, &r, &c);
int row = getRow(n, r);
int col = getCol(m, c);
if (light) {
//켜져있을때 (a||!b)&&(!a||b)
adj[row * 2 + 1].push_back(col * 2 + 1);
adj[col * 2].push_back(row * 2);
adj[row * 2].push_back(col * 2);
adj[col * 2 + 1].push_back(row * 2 + 1);
}
else {
//꺼져있을때 (a||b)&&(!a||!b)
adj[row * 2 + 1].push_back(col * 2);
adj[col * 2 + 1].push_back(row * 2);
adj[row * 2].push_back(col * 2 + 1);
adj[col * 2].push_back(row * 2 + 1);
}
}
}
for (int n = 0;n < idx * 2;n++) {
if (!visit[n]) dfs(n);
}
bool ans = true;
for (int n = 0;n < idx*2;n+=2) {
if (scc[n] == scc[n + 1]) {
ans = false;
break;
}
}
printf("Case #%d\n", t);
if (ans) {
vector<pair<int, int>> s;
vector<int> ret(MAX, -1);
for (int n = 0;n < idx * 2;n++) s.push_back(make_pair(-scc[n], n));
sort(s.begin(), s.end());
for (auto &i : s) {
int here = i.second;
if (ret[here / 2] != -1) continue;
ret[here / 2] = (here & 1);
}
for (int n = 0;n < idx;n++) {
if (ret[n]) {
if (save[n][0]) printf("C%02d%02d ", save[n][1], save[n][2]);
else printf("R%02d%02d ", save[n][1], save[n][2]);
}
}
}
else printf("Impossible");
printf("\n");
}
return 0;
}
| cs |
댓글 없음:
댓글 쓰기