BOJ 5831 : Blink

• 문제 링크 : boj.kr/5831
• 난이도 : G3
• 태그 : 그래프 이론, 브루트포스, 비트마스킹

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    ll n, b;
    cin >> n >> b;
    vector<int> visit(1 << n);
    int curr = 0;
    for(int i = 0; i < n; i++) {
        curr = curr << 1;
        int input;
        cin >> input;
        curr += input;
    }
    visit[curr] = 1;
    while(b) {
        int toggle = curr >> 1;
        if(curr%2) toggle += (1 << (n-1));
        int next = curr ^ toggle;
        if(visit[next]) {
            b %= (visit[curr]+1 - visit[next]);
        }
        if(b) {
            visit[next] = visit[curr]+1;
            curr = next;
            b--;
        }
    }
    bitset<16> ans(curr);
    for(int i = n-1; i >= 0; i--) cout << ans[i] << "\n";

    return 0;
}

---

풀이

전구의 상태를 비트로 나타내면 다음 상태를 쉽게 구할 수 있다.

전구의 상태를 그래프로 표현하면 정점과 간선의 개수가 같으므로 사이클이 발생한다.

가능한 상태의 수가 2^N이므로 O(2^N)으로 사이클을 찾을 수 있고, 사이클의 길이만큼 남은 b를 나누어 주면 되므로 총 O(2^N)의 시간복잡도로 문제를 해결할 수 있다.