BOJ 1625 - 조명기구
문제의 단순화Permalink
일반성을 잃지않고 결과 상태로 가는 방법이 있을 때, 그 방법에서 행을 switch하는 연산을 모두 먼저 하고 시작해도 상관이 없다는걸 파악하자.
불가능한 경우 파악Permalink
행으로 검사Permalink
언제 불가능할까? 초기 상태의 특정 행에 이 개 있고, 이 개 있다고 하자.
최종 상태의 특정 행에 이 개나 개가 있지 않다면 그 행을 switch해도 절대 합이 같아질 수 없기 때문에 불가능하다.
열로 검사Permalink
이건 당장은 파악할 수 없고 직접 알고리즘을 전개하면서 모든 경우에서 브루트포스가 실패한다면 안된다고 출력해준다.
행 switch 연산Permalink
어떤 행들이 switch가 되어야 할까? 우선 특정 행은 항상 번이나 번만 switch가 되면 된다.
우선 특정 행에 1의 초기 상태의 합이 이고 결과 상태의 합도 라면 바꿀 필요 없다.
반대로 결과 상태의 합이 라면 바꿔야 한다.
근데, 고려해야 할 하나의 경우가 있다.
만약 가 짝수이고 라면 이 행을 switch를 해야할까 말아야할까?
결론은 알 수 없다이다. 따라서 이러한 행들은 따로 관리한다.
알고리즘 전개와 시간복잡도Permalink
이렇게 행들에 대해서 전처리를 마치고나면 실제로 알고리즘을 어떻게 풀지 생각해봐야 한다.
이기 때문에 이상의 알고리즘은 쓸 수가 없다.
이전에 관리해둔 switch할 수 있는 행의 수는 최대 개이기 때문에 이미 특정 행들을 switch 할지 말지 결정하는것만 해도 의 시간복잡도가 나오고 열들을 swap하는 경우의 수는 이기 때문에 의 미친시간복잡도가 나온다.
따라서 우리는 해를 줄여야한다.
그렇다. 이 문제는 백트랙킹이다.
백트랙킹의 내가 내린 정의는 모든 경우의 수 중에 해가 존재한다면, 경우의 수의 특정 부분 집합만 살펴봐도 해가 항상 거기에 있다는 것을 증명하고, 그 부분 집합만 탐색하는 알고리즘이다.
이 문제에서의 핵심 아이디어는 초기 상태에서 어떤 열을 최종 상태의 첫 번째 열로 고정하면 더 이상 그 어떤 행도 switch를 할 수 없기 때문에 나머지 열들끼리 매칭만 되는지 확인해주면 된다는 것에 있다.
어떤 열을 최종 상태의 첫 번째 열로 고정시키기 위해 그 열이 최종 상태의 첫 번째 열이 될 수 있는지부터 검사한다.
검사하는 과정은 일단 행을 쭉 보며 숫자가 같으면 넘기고 숫자가 다르면 우리가 이전에 관리했던 switch할 수 있는 행인지 검사하고, 그렇다면 switch하면 된다.
이렇게 switch를 할지 말지 결정해버리면 더 이상 그 어떤 행도 switch를 더이상 못한다. 더 해버리면 기껏 맞춰놓은 첫 번째 열이 달라지기 때문이다.
이제 남은 개의 초기 상태의 열들과 최종 상태의 열들이 배열을 했을 때 일치할 수 있는지를 검사하고, 만약 가능하다면 정답을 찾은 것이 된다.
따라서 시간복잡도는 정도 된다. 이 붙은 이유는 남은 열들끼리 일치할 수 있는지 검사하는 과정에서 정렬을 쓰면 편하기 때문이다.
모든 열을 최종 상태의 첫 열로 맞춰보는 시도의 횟수 에 정렬하는 과정 에 열들을 정렬하고 매칭시켜보기 때문에 가 붙었다.
시간복잡도가 라서 애매하다고 생각할 수 있겠지만 실제로 저만큼 돌 일이 없다는 것을 생각해보면 알 수 있을 것이다.
구현 팁Permalink
구현에 손이 많이 가는 문제이다.
- 최종 상태의 첫 열이 될 초기 상태의 열을 고정하고 row 들을 switch 했다면 그 상태 그대로 개의 열들을 검사해주면 된다.
- 열에 대해서 배열로 가지는
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