BOJ - 두 개의 문(17453)

문제(링크)

문과 스위치의 값을 bitset을 이용해 bit값으로 바꿔줍니다.
그 뒤, 스위치들에 대하여 모든 경우를 탐색하면서 현재 문의 상태로 갈 수 있는 년도를
구합니다.
(문을 바꿔가며 -> 문과 스위치의 ^ 연산)

년도는 n 이 100이하이므로 100년을 시작년도로 생각하였습니다.
방문 배열을 만들어 현재 어떤 스위치를 켰는지(bitMask 이용)에 대한 방문 여부를
걸러줍니다. 그렇게 하면 하나의 스위치 상태에 대해 하나의 년도만 나오게 됩니다.

즉, rt[해당 년도] = 스위치의 bitMask
100 - N 년부터 100 + N 년까지 스위치의 bitMask를 적절히 출력하면 됩니다.

#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<vector>
#include<bitset>
using namespace std;
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pii pair<int, int>;

int N, M;
bitset<101> swit[21];
bitset<101> door;
int rt[202];
int sizeY[202];
bool visit[1048577];

void BF(bitset<101> now, int cnt, int switBit) {
 if (cnt > M) return;
 if (visit[switBit]) return;
 visit[switBit] = true;
 for (int i = 1; i <= M; i++)
 {
  int bit = (1 << (i - 1));
  BF(now ^ swit[i], cnt + 1, switBit | bit);
 }

 int year = 100 - N + (now.count() * 2);

 sizeY[year] = cnt;

 rt[year] = switBit;
}

int main(void) {
 FIO;

 cin >> N >> M;

 string start;
 cin >> start;

 for (int i = 0; i < start.size(); i++)
 {
  if (start.at(i) == '1')
   door.set(100 - i, true);
 }
 for (int i = 1; i <= M; i++)
 {
  string s;
  cin >> s;

  for (int j = 0; j < s.size(); j++)
  {
   if (s.at(j) == '1')
    swit[i].set(100 - j, true);
  }
 }
 for (int i = 0; i < 202; i++)
 {
  sizeY[i] = -1;
 }

 BF(door, 0, 0);

 int y = 100 - N;
 while (y <= 100 + N) {
  cout << sizeY[y] << " ";

  int cnt = 1;
  while (rt[y] != 0) {
   if ((rt[y] & 1) != 0)
    cout << cnt << " ";

   cnt++;
   rt[y] = rt[y] >> 1;
  }
  cout << "\n";
  y++;
 }
}