BOJ 1625 - 조명기구
문제의 단순화
일반성을 잃지않고 결과 상태로 가는 방법이 있을 때, 그 방법에서 행을 switch하는 연산을 모두 먼저 하고 시작해도 상관이 없다는걸 파악하자.
불가능한 경우 파악
행으로 검사
언제 불가능할까? 초기 상태의 특정 행에 $1$ 이 $k$개 있고, $0$이 $X-k$ 개 있다고 하자.
최종 상태의 특정 행에 $1$ 이 $k$개나 $X-k$개가 있지 않다면 그 행을 switch해도 절대 합이 같아질 수 없기 때문에 불가능하다.
열로 검사
이건 당장은 파악할 수 없고 직접 알고리즘을 전개하면서 모든 경우에서 브루트포스가 실패한다면 안된다고 출력해준다.
행 switch 연산
어떤 행들이 switch가 되어야 할까? 우선 특정 행은 항상 $0$번이나 $1$번만 switch가 되면 된다.
우선 특정 행에 1의 초기 상태의 합이 $k$ 이고 결과 상태의 합도 $k$ 라면 바꿀 필요 없다.
반대로 결과 상태의 합이 $X-k$ 라면 바꿔야 한다.
근데, 고려해야 할 하나의 경우가 있다.
만약 $X$가 짝수이고 $k=\dfrac{X}{2}$ 라면 이 행을 switch를 해야할까 말아야할까?
결론은 알 수 없다이다. 따라서 이러한 행들은 따로 관리한다.
알고리즘 전개와 시간복잡도
이렇게 행들에 대해서 전처리를 마치고나면 실제로 알고리즘을 어떻게 풀지 생각해봐야 한다.
$N \le 256$ 이기 때문에 $O(N^4)$ 이상의 알고리즘은 쓸 수가 없다.
이전에 관리해둔 switch할 수 있는 행의 수는 최대 $O(N)$개이기 때문에 이미 특정 행들을 switch 할지 말지 결정하는것만 해도 $O(2^N)$의 시간복잡도가 나오고 열들을 swap하는 경우의 수는 $N!$ 이기 때문에 $O(2^N \cdot N!)$의 미친시간복잡도가 나온다.
따라서 우리는 해를 줄여야한다.
그렇다. 이 문제는 백트랙킹이다.
백트랙킹의 내가 내린 정의는 모든 경우의 수 중에 해가 존재한다면, 경우의 수의 특정 부분 집합만 살펴봐도 해가 항상 거기에 있다는 것을 증명하고, 그 부분 집합만 탐색하는 알고리즘이다.
이 문제에서의 핵심 아이디어는 초기 상태에서 어떤 열을 최종 상태의 첫 번째 열로 고정하면 더 이상 그 어떤 행도 switch를 할 수 없기 때문에 나머지 열들끼리 매칭만 되는지 확인해주면 된다는 것에 있다.
어떤 열을 최종 상태의 첫 번째 열로 고정시키기 위해 그 열이 최종 상태의 첫 번째 열이 될 수 있는지부터 검사한다.
검사하는 과정은 일단 행을 쭉 보며 숫자가 같으면 넘기고 숫자가 다르면 우리가 이전에 관리했던 switch할 수 있는 행인지 검사하고, 그렇다면 switch하면 된다.
이렇게 switch를 할지 말지 결정해버리면 더 이상 그 어떤 행도 switch를 더이상 못한다. 더 해버리면 기껏 맞춰놓은 첫 번째 열이 달라지기 때문이다.
이제 남은 $X-1$ 개의 초기 상태의 열들과 최종 상태의 열들이 배열을 했을 때 일치할 수 있는지를 검사하고, 만약 가능하다면 정답을 찾은 것이 된다.
따라서 시간복잡도는 $O(X \cdot Y \cdot X \log X)$ 정도 된다. $\log N$이 붙은 이유는 남은 열들끼리 일치할 수 있는지 검사하는 과정에서 정렬을 쓰면 편하기 때문이다.
모든 열을 최종 상태의 첫 열로 맞춰보는 시도의 횟수 $X$에 정렬하는 과정 $X \log X$ 에 열들을 정렬하고 매칭시켜보기 때문에 $Y$ 가 붙었다.
시간복잡도가 $X, Y \le 256$ 라서 애매하다고 생각할 수 있겠지만 실제로 저만큼 돌 일이 없다는 것을 생각해보면 알 수 있을 것이다.
구현 팁
구현에 손이 많이 가는 문제이다.
- 최종 상태의 첫 열이 될 초기 상태의 열을 고정하고 row 들을 switch 했다면 그 상태 그대로 $X$ 개의 열들을 검사해주면 된다.
- 열에 대해서 배열로 가지는
src_col,dst_col을 지정함으로 써 쉽게 연산이 가능하다. - 두 열 집합이 동일하게 매칭되는지 검사하기 위해 정렬을 써서 쉽게 할 수 있다.
void solve() {
int Y,X;cin>>Y>>X;vvi a(Y, vi(X)), b(Y,vi(X)); fv2(a);fv2(b);
vector<pi> ans;
vi y_swapable(Y);
auto toggle_row = [&](int y) {
for(int x = 0; x < X; x++) a[y][x] = a[y][x] == 0 ? 1 : 0;
};
for(int y = 0; y < Y; y++){
int asum = acc(a[y]), bsum = acc(b[y]);
if(asum == bsum && asum * 2 == X) y_swapable[y] = 1;
else if(asum != bsum) {
if(asum + bsum != X) {
cout << -1; exit(0);
}
ans.pb({-1, y});
toggle_row(y);
}
}
// match one of source col with first target col
int find_answer = 0;
for(int tx = 0; tx < X; tx++) { // 모든 열을 돌며 최종 상태의 첫 열이 될 수 있는지 검사
int can = 1;
vi will_be_swapped_y;
for(int y = 0; y < Y; y++){
if(a[y][tx] == b[y][0]) continue;
if(!y_swapable[y]) {
can = 0; break;
}else {
will_be_swapped_y.pb(y);
}
}
if(!can) continue;
for(int swap_y: will_be_swapped_y) toggle_row(swap_y);
// test other columns
vvi src_cols(X), dst_cols(X);
for(int x = 0; x < X; x++) {
for(int y = 0; y < Y; y++) {
src_cols[x].pb(a[y][x]), dst_cols[x].pb(b[y][x]);
}
}
auto src_cols2 = src_cols, dst_cols2 = dst_cols;
sort(all(src_cols2)), sort(all(dst_cols2));
if(src_cols2 == dst_cols2) {
for(int swap_y: will_be_swapped_y) ans.pb({-1, swap_y});
for(int x1 = 0; x1 < X; x1++) {
for(int x2 = x1; x2 < X; x2++) {
if(dst_cols[x1] == src_cols[x2]) {
swap(src_cols[x1], src_cols[x2]);
if(x1 != x2) ans.pb({x1, x2});
break;
}
}
}
find_answer = 1;
break;
}
for(int swap_y: will_be_swapped_y) toggle_row(swap_y);
}
if(!find_answer) {
cout << -1; exit(0);
}
cout << sz(ans) << endl;
for(auto&[u,v]: ans) {
if(u == -1) cout << 0 << ' ' << v + 1 << endl;
else cout << 1 << ' ' << u + 1 << ' ' << v + 1 << endl;
}
}
Comments