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;
   }

}

Tags:

Categories:

Updated:

Comments