부울 배열 퍼즐이란?
부울(Boolean) 배열 퍼즐은 두 개의 요소로 구성된 배열의 모든 값을 0으로 바꾸는 문제입니다. 이 배열에는 반드시 하나의 요소는 0이며, 나머지 하나는 0일 수도 있고 아닐 수도 있습니다.
이 퍼즐을 해결하려면 프로그램이 0이 아닌 요소를 찾아내어 그 값을 0으로 변경해야 합니다.
해결을 위한 제약 조건
이 퍼즐에는 다음과 같은 까다로운 제약 조건이 주어집니다.
- 허용되는 연산은 보수(complement) 연산뿐이며, 그 외의 연산은 사용할 수 없습니다.
- 반복문(for, while 등)과 조건문(if, switch 등)은 사용할 수 없습니다.
- 직접 대입(direct assignment) 역시 허용되지 않습니다.
부울 배열 퍼즐 해결 프로그램
아래는 위 제약 조건을 모두 지키면서 문제를 해결하는 C++ 코드입니다.
#include <iostream>
using namespace std;
void makeZero(int a[2]) {
a[ a[1] ] = a[ !a[1] ];
}
int main() {
int a[] = {1, 0};
makeZero(a);
cout<<"arr[0] = "<<a[0]<<endl;
cout<<"arr[1] = "<<a[1];
return 0;
}
실행 결과
arr[0] = 0
arr[1] = 0
동작 원리
핵심 코드인 a[ a[1] ] = a[ !a[1] ];가 어떻게 작동하는지 살펴보겠습니다.
- a[1]이 0인 경우: a[a[1]]은 a[0]을 가리키고, !a[1]은 1이므로 a[!a[1]]은 a[1]을 가리킵니다. 따라서 a[0]에 a[1](=0)의 값이 대입됩니다.
- a[1]이 1인 경우: a[a[1]]은 a[1]을 가리키고, !a[1]은 0이므로 a[!a[1]]은 a[0]을 가리킵니다. 따라서 a[1]에 a[0](=0)의 값이 대입됩니다.
배열에는 항상 최소 하나의 0이 존재하기 때문에, 어떤 경우에도 두 요소는 모두 0이 됩니다.
대안적인 해결 방법
위 방법 외에도 다른 방식으로 문제를 해결할 수 있습니다. 예를 들어 아래 코드는 부정(negation) 연산 없이도 동일한 결과를 얻습니다.
a[ a[1] ] = a[ a[0] ]
이 방식 역시 인덱스 자체를 포인터처럼 활용하여, 어느 요소가 0이든 결국 두 값이 모두 0으로 수렴하도록 만듭니다. 제약 조건이 많은 퍼즐이지만, 인덱싱과 보수 연산을 창의적으로 조합하면 반복문이나 조건문 없이도 우아하게 해결할 수 있다는 점이 흥미로운 부분입니다.