C++로 각 행에서 숫자를 선택해 XOR 값이 0보다 크게 만들 수 있는지 확인하는 방법

N × M 크기의 2차원 배열이 주어졌을 때, 모든 행에서 숫자를 하나씩 선택하여 선택된 요소들의 XOR 값이 0이 아닌(즉, 0보다 큰) 값이 되도록 할 수 있는지 확인하는 것이 이 글의 목표입니다.

예를 들어 다음과 같은 행렬이 있다고 가정해 보겠습니다.

첫 번째 행에서는 7, 두 번째 행에서는 10을 선택하면 7 XOR 10의 결과가 되는데, 서로 다른 두 수의 XOR은 절대 0이 될 수 없으므로 답은 0이 아닌 값이 됩니다.

문제 해결 접근 방법

이 문제의 풀이법은 의외로 간단합니다. 핵심 아이디어는 다음 두 가지 조건을 순서대로 확인하는 것입니다.

• 1단계: 각 행의 첫 번째 열 요소들을 모두 XOR한 값이 0이 아닌지 확인합니다. 0이 아니라면 이미 조건을 만족하므로 바로 true를 반환합니다.
• 2단계: 첫 번째 열의 XOR이 0이라면, 어떤 행에라도 첫 번째 열의 값과 다른 요소가 존재하는지 확인합니다. 존재한다면 그 행의 선택을 다른 값으로 바꿀 수 있고, 이때 전체 XOR은 (기존 값 XOR 새로운 값)이 되어 서로 다른 두 수의 XOR이므로 반드시 0이 아닙니다. 따라서 true를 반환합니다.
• 3단계: 위 두 조건이 모두 만족되지 않는다면, 어떤 방식으로 선택하더라도 XOR이 0이 될 수밖에 없으므로 false를 반환합니다.

C++ 구현 예제

#include<iostream>
using namespace std;
#define N 2
#define M 3

bool isXORnonZero(int matrix[N][M]) {
   int xor_value = 0;
   // 1단계: 각 행의 첫 번째 열 요소들의 XOR 계산
   for (int i = 0; i < N; i++) {
      xor_value ^= matrix[i][0];
   }
   if (xor_value != 0)
      return true;
   // 2단계: 임의의 행에 첫 번째 열과 다른 값이 존재하는지 확인
   for (int i = 0; i < N; i++) {
      for (int j = 1; j < M; j++) {
         if (matrix[i][j] != matrix[i][0])
         return true;
      }
   }
   // 두 조건 모두 실패하면 XOR을 0이 아니게 만들 수 없음
   return false;
}

int main() {
   int mat[N][M] = {
      { 7, 7, 7 },
      { 10, 10, 7 }
   };
   if (isXORnonZero(mat))
      cout << "XOR has non-zero value";
   else
      cout << "XOR has zero value";
}

출력 결과

XOR has non-zero value

복잡도 분석

위 알고리즘은 배열의 모든 요소를 최대 한 번씩만 확인하므로 시간 복잡도는 O(N × M)이며, 추가적인 저장 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다. 행렬의 크기가 커져도 효율적으로 동작하는 것이 이 방법의 장점입니다.