[BOJ 16450 // C++] Interruptores

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 16450번 문제인 Interruptores이다.
문제는 아래 링크를 확인하자.

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

 

가장 쉽게 떠울릴 수 있는 접근으로, 모든 불이 꺼질 때까지 스위치를 작동시키는 것을 시도하고 그러한 때가 존재한다면 그 때까지의 스위치 작동 횟수를 답으로 삼는 것이 있다. 이 접근방법의 문제점은 모든 불을 끌 수 없는 경우 스위치를 끝없이 작동시키게 되어 문제를 해결할 수 없다는 것인데, 어떤 조건으로 불을 끌 수 없는 경우 반복을 중단시킬 수 있다면 이러한 문제를 해소할 수 있다. 모든 불이 꺼지는 경우가 없는 경우라는 것을 확신하기 위해 스위치를 몇 번 작동해봐야 할까?

 

위 질문의 답은 스위치의 특징을 관찰하면 쉽게 알아낼 수 있다. 구체적으로, 각 스위치는 짝수 번 작동시키면 작동시키지 않은 것과 같은 모습을 보임을 이용하면, 모든 스위치를 정확히 2바퀴 작동시키면 모든 불의 상태가 초기와 똑같아지고 그 이후로 나타나는 불의 상태는 앞서 나온 형태의 반복임을 알 수 있다.

 

위 관찰을 이용해 불을 켜고 끄는 시뮬레이션을 진행하는 코드를 작성하여 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

int N, M;
int cnt, sgn[1001];
vector<int> vec[1000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	int K; cin >> K; cnt = K;
	while (K--) {
		int x; cin >> x;
		sgn[x] = 1;
	}
	for (int i = 0; i < N; i++) {
		cin >> K;
		while (K--) {
			cin >> vec[i].emplace_back();
		}
	}

	for (int i = 0; i < 2000; i++) {
		for (auto &x : vec[i % N]) {
			if (sgn[x]) sgn[x] = 0, cnt--;
			else sgn[x] = 1, cnt++;
		}
		if (!cnt) {
			cout << i + 1;
			return 0;
		}
	}

	cout << -1;
}