C++에서 보드를 체스판으로 변환하는 최소 이동 횟수 구하기

N × N 크기의 보드가 있고, 보드에는 0과 1만 들어 있다고 가정해 봅시다. 한 번의 이동에서는 임의의 두 행(row)을 서로 맞바꾸거나, 임의의 두 열(column)을 서로 맞바꿀 수 있습니다. 목표는 최소 이동 횟수로 이 보드를 '체스판' 형태로 변환하는 것이며, 변환이 불가능하다면 -1을 반환해야 합니다.

예를 들어 입력이 아래와 같다고 해보겠습니다.

이때 출력은 2가 됩니다. 첫 번째 이동에서 앞쪽 두 열을 서로 교환하면 보드는 다음과 같이 바뀝니다.

이어서 두 번째 행과 세 번째 행을 교환하면,

드디어 원하는 체스판이 완성됩니다.

문제 해결 접근 방식

체스판 패턴의 특성상 모든 행은 두 종류(0101… 또는 1010…) 중 하나여야 하고, 열 역시 마찬가지입니다. 덕분에 첫 번째 행과 첫 번째 열만 검사하면 전체 보드의 변환 가능 여부와 필요한 교환 횟수를 O(n²) 시간 안에 판단할 수 있습니다. 구체적인 해결 단계는 다음과 같습니다.

n을 보드 b의 크기로 설정합니다.
이중 반복문으로 모든 칸 (i, j)를 검사하면서, b[0][0] XOR b[0][j] XOR b[i][0] XOR b[i][j]의 값이 0이 아니라면 -1을 반환합니다. 이 조건이 깨지면 어떤 행·열 교환으로도 체스판을 만들 수 없습니다.
rowSum, colSum, rowSwap, colSwap을 0으로 초기화합니다.
i를 0부터 n-1까지 순회하며 다음 값들을 누적합니다.
- rowSum += b[i][0]
- colSum += b[0][i]
- b[i][0]이 i mod 2와 같으면 rowSwap을 1 증가
- b[0][i]가 i mod 2와 같으면 colSwap을 1 증가
rowSum이 n/2도 아니고 (n+1)/2도 아니라면 -1을 반환합니다.
colSum이 n/2도 아니고 (n+1)/2도 아니라면 -1을 반환합니다.
n이 홀수인 경우: colSwap이 홀수이면 colSwap := n - colSwap으로, rowSwap이 홀수이면 rowSwap := n - rowSwap으로 보정합니다.
n이 짝수인 경우: colSwap := min(colSwap, n - colSwap), rowSwap := min(rowSwap, n - rowSwap)을 적용해 더 작은 쪽을 선택합니다.
최종적으로 (rowSwap + colSwap) / 2를 반환합니다.

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int movesToChessboard(vector<vector<int>>& b) {
      int n = b.size();
      for(int i = 0; i < n; i++){
         for(int j = 0; j < n; j++){
            if(b[0][0] ^ b[0][j] ^ b[i][0] ^ b[i][j]) return -1;
         }
      }
      int rowSum = 0;
      int colSum = 0;
      int rowSwap = 0;
      int colSwap = 0;
      for(int i = 0; i < n; i++){
         rowSum += b[i][0];
         colSum += b[0][i];
         rowSwap += b[i][0] == i % 2;
         colSwap += b[0][i] == i % 2;
      }
      if(rowSum != n/2 && rowSum != (n + 1)/2)return -1;
      if(colSum != n/2 && colSum != (n + 1)/2)return -1;
      if(n % 2 == 1){
         if(colSwap % 2) colSwap = n - colSwap;
         if(rowSwap % 2) rowSwap = n - rowSwap;
      }else{
         colSwap = min(colSwap, n - colSwap);
         rowSwap = min(rowSwap, n - rowSwap);
      }
      return (rowSwap + colSwap)/2;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1,1,0},{0,1,1,0},{1,0,0,1},{1,0,0,1}};
   cout << (ob.movesToChessboard(v));
}

입력

{{0,1,1,0},{0,1,1,0},{1,0,0,1},{1,0,0,1}};