백준 5998 (C++) Lights

최초 업로드: 2025-10-26 13:48:12

최근 수정 시간: 2025-10-26 13:48:12

게시자: rlatjwls3333

카테고리: 백준

# [Platinum V] Lights

[문제 링크](https://www.acmicpc.net/problem/5998)

## 문제 설명

Bessie and the cows were playing games in the barn, but the power was reset and the lights were all turned off. Help the cows get all the lights back on so they can resume their games.

The N (1 <= N <= 35) lights conveniently numbered 1..N and their switches are arranged in a complex network with M (1 <= M <= 595) clever connection between pairs of lights (see below).

Each light has a switch that, when toggled, causes that light -- and all of the lights that are connected to it -- to change their states (from on to off, or off to on).

Find the minimum number of switches that need to be toggled in order to turn all the lights back on.

It's guaranteed that there is at least one way to toggle the switches so all lights are back on.

## 입력

<ul>
	<li>Line 1: Two space-separated integers: N and M.</li>
	<li>Lines 2..M+1: Each line contains two space-separated integers representing two lights that are connected. No pair will be repeated.</li>
</ul>

## 출력

Line 1: A single integer representing the minimum number of switches that need to be flipped in order to turn on all the lights.

## 풀이
왼쪽 절반에 대해 모든 조합에 대해 비트마스킹으로 방문 조합을 맵에 저장하고, 오른쪽 절반에 대해 최소 전부 방문하는 조합의 최소 cnt를 세주었다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int n, m;
ll bit[35];
bool conn[35][35];
int minCnt=35;
unordered_map<ll, int> vals;

void back1(int start=0, ll val=0, int cnt=0) {
 if(!vals.count(val)) vals[val]=cnt;
 else vals[val] = min(vals[val], cnt);
 if(start==n/2) return;
 for(int i=start;i<n/2;i++) back1(i+1, val^bit[i], cnt+1);
}

void back2(int start=n/2, ll val=0, int cnt=0) {
 if(vals.count(val^((1LL<<n)-1))) {
 minCnt = min(minCnt, vals[val^((1LL<<n)-1)]+cnt);
 return;
 }
 if(start==n) return;
 for(int i=start;i<n;i++) back2(i+1, val^bit[i], cnt+1);
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 cin >> n >> m;
 for(int i=0;i<n;i++) conn[i][i]=true;
 while(m--) {
 int a, b; cin >> a >> b;
 conn[a-1][b-1]=conn[b-1][a-1]=true;
 }

for(int i=0;i<n;i++) {
 for(int j=0;j<n;j++) {
 if(conn[i][j]) bit[i] |= 1LL<<j;
 }
 }
 back1();
 back2();
 cout << minCnt;
}
```