[C++] 백준 25376번: 이상한 스위치

문제 링크

25376번: 이상한 스위치

문제 요약

스위치들이 놓여 있을 때, 꺼져 있는 스위치만 켜서 모든 스위치를 켜져 있는 상태로 만들어야 한다. 특정한 스위치를 켜게 된다면 그 스위치의 영향을 받는 모든 스위치의 상태가 반전되게 된다. 스위치가 모두 켜져 있도록 만들기 위해서 스위치를 누르는 횟수의 최솟값을 출력해야 한다. 만약 불가능하다면 -1을 출력해야 한다.

접근 방법

비트마스킹을 이용하면 스위치들의 상태를 큐에 넣어서, 너비 우선 탐색으로 해결할 수 있습니다.

초기 스위치의 상태를 비트로 보고, 시프트 연산자와 OR 연산을 이용해서 하나의 수로 만들어 줍니다. 그리고 스위치 사이의 인접 관계는 인접 리스트로 만들어 줍니다.

이제 BFS를 돌리면 됩니다. 반복문을 통해서 현재 수에서 0인 비트를 AND 연산으로 찾은 뒤에, 해당 비트를 OR 연산으로 1로 바꿔주고, 인접 관계에 있는 모든 비트를 XOR 연산을 통해서 반전시켜줍니다. 만약 그렇게 탄생한 수를 방문한 적이 있다면 넘어가고, 그렇지 않다면 큐에 넣어주면 됩니다.

만약 이 과정에서 $2^N - 1$에 도달하게 된다면 횟수를 출력해줍니다. BFS가 끝나고도 도달하지 못한다면 -1을 출력해주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;
using std::cout;

const int MAX = 20;
bool visited[1 << MAX];
vector<int> adj[MAX];

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;

	int start = 0;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		start |= a << i;
	}

	for (int i = 0; i < n; i++) {
		int c;
		cin >> c;

		for (int j = 0; j < c; j++) {
			int b;
			cin >> b;
			adj[i].push_back(b - 1);
		}
	}

	queue<pair<int, int>> q;
	q.push({ start, 0 });
	visited[start] = true;

	while (!q.empty()) {
		auto now = q.front();
		q.pop();

		if (now.first == (1 << n) - 1) {
			cout << now.second << '\n';
			return 0;
		}

		for (int i = 0; i < n; i++) {
			int pos = 1 << i;
			if (!(now.first & pos)) {
				int next = now.first;
				next |= pos;

				for (auto& j : adj[i])
					next ^= 1 << j;

				if (!visited[next]) {
					visited[next] = true;
					q.push({ next, now.second + 1 });
				}
			}
		}
	}

	cout << -1 << '\n';
	return 0;
}