2196 - 이진수 XOR

문제 링크

---

https://www.acmicpc.net/problem/2196

문제 요약

---

\(B\)자리의 2진수 \(E\)개가 주어진다. 이제 이진수를 두개씩 선택해서 XOR을 진행한다. 이 과정에서 만들어지는 수 또한 선택할 수 있다. 이렇게 해서 만들 수 있는 이진수들 중 이진수 \(S\)와 해밍거리가 가장 가까운 수를 출력하는 문제다.

문제 풀이

---

이 문제를 어렵게 만드는 요소 중 하나는 XOR과정에서 만들어진 수 또한 XOR연산에 사용할 수 있다는 점이다. 하지만 XOR의 특징을 잘 생각해 본다면 이 문제를 쉽게 해결할 수 있다.

\(A\), \(B\), \(C\), \(D\) 네 개의 이진수가 있다고 가정하자. \(A \oplus B\)를 통해 \(X\)를 만들고 \(C \oplus D\)를 통해 \(Y\)를 만들고 다시 \(X \oplus Y\)를 통해 \(Z\)를 만들었다고 하자. 이 때 한가지 질문을 해 보자. 과연 XOR하는 순서가 상관이 있는지. XOR은 결합법칙과 교환법칙이 성립하기 때문에 \(Z\)를 만들기 위해서는 순서가 중요하지 않다. 또한 \(A \oplus B \oplus C\)와 \(D\)를 XOR해도 \(Z\)가 나온다. 따라서 우리는 어떠한 수들을 만들어 나갈때 기존에 주어진 이진수들만 XOR해 나가면 된다는 사실을 깨달을 수 있다.

그렇다면 이러한 탐색과정을 어떻게 해 나갈 수 있을까? 우리는 이 문제를 \(BFS\)를 통해 해결할 수 있다. \(BFS\)를 돌면서 방문하는 숫자들은 XOR연산들을 통해 만들 수 있는 숫자들이 될 것이고 이 숫자들에서 다시 주어진 이진수들을 XOR해 나가면 결과적으로 만들 수 있는 모든 숫자들을 탐색할 수 있을것이다. \(BFS\)를 돌면서 방문하는 숫자들은 최대 \(O(2^B)\)개가 될 것이고 이는 그리 큰 숫자가 아니므로 충분히 가능하다.

마지막으로 주의해야 할 점은 출력해야 되는 수 조건이 조금 까다롭다는 점이다. 첫 번째로는 해밍 거리, 두 번째는 연산 횟수, 세 번째는 사전순 순서로 답을 결정해야 한다.

소스 코드

---

#include <stdio.h>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>

using namespace std;

int B, E, S;
char A[20];
vector<int> node;

int toInt(char* str) {
  int ret = 0;
  for (int i = 0 ; str[i] ; ++i) {
    ret <<= 1;
    ret += str[i] - '0';
  }
  return ret;
}

vector<int> getDist() {
  vector<int> dist(2 << B, 0);
  queue<int> q;
  for (int x : node) {
    for (int y : node) {
      if (!dist[x ^ y]) {
        dist[x ^ y] = 1;
        q.push(x ^ y);
      }
    }
  }
  
  while (!q.empty()) {
    int here = q.front();
    q.pop();
    
    for (int val : node) {
      int there = here ^ val;
      if (!dist[there]) {
        dist[there] = dist[here] + 1;
        q.push(there);
      }
    }
  }
  
  return dist;
}

int getHamming(int x, int y) {
  int ret = 0 ;
  for (int i = 0 ; i < B ; ++i) {
    ret += (x & 1) ^ (y & 1);
    x >>= 1;
    y >>= 1;
  }
  return ret;
}

int main() {
  scanf("%d%d%s", &B, &E, A);
  S = toInt(A);
  for (int i = 0 ; i < E ; ++i) {
    scanf("%s", A);
    node.push_back(toInt(A));
  }
  
  vector<tuple<int, int, int>> ans;
  vector<int> dist = getDist();
  for (int i = 0 ; i < (1 << B) ; ++i) {
    if (dist[i]) {
      ans.emplace_back(getHamming(S, i), dist[i], i);
    }
  }
  sort(ans.begin(), ans.end());
  
  printf("%d\n", get<1>(ans[0]));
  int val = get<2>(ans[0]);
  for (int i = B - 1 ; i >= 0 ; --i) {
    A[i] = (val & 1) + '0';
    val >>= 1;
  }
  A[B] = '\0';
  printf("%s\n", A);
}