[백준 16960번] 스위치와 램프 풀이

16960번: 스위치와 램프

 

N개의 스위치와 M개의 램프가 있다. N개의 스위치를 모두 누르면 M개의 램프 모두가 켜진다고 명시되어있기 때문에 모든 램프는 적어도 한번씩 N개의 스위치에 연결되어있다. 

 

문제를 풀 수 있는 두가지 방법이 있는데, 첫째는 모든 램프가 꺼져있다고 가정하고 스위치를 한개씩 켜보는 것이다. 램프가 모두 켜질 때까지 최소로 켜야 하는 스위치 개수를 구해 이를 N-1과 비교하는 방법이다. 그러나, 해당 방법으로 문제를 풀면 정말 복잡하다. 따라서 모든 램프가 켜져 있다고 가정하고, 스위치를 한개씩 꺼보는 것이다. 모든 스위치를 켰을 때는 모든 램프에 불이 들어와있을 것이므로, 하나의 스위치를 껐을 때에도 모든 램프에 불이 들어와 있는지 확인한다. 만약 그렇다면, N-1개의 스위치만을 켰을 때 모든 램프의 전원을 킬 수 있는 것이기에 1을 출력한다. 

 

문제에서 주어진 데이터를 입력받은 후, 이중벡터 vSwitch에 각 스위치가 켤 수 있는 램프 번호를 저장하고, vLamp는 램프를 기준으로 각 램프를 켤 수 있는 스위치를 저장한다.

 

예를 들어 입력이 다음과 같다고 할 때,

 

4 5
3 1 3 5
1 2
3 3 4 5
1 1

 

vSwitch와 vLamp는 각각 다음과 같다. 참고로, idx 번째 인덱스에는 idx번째 스위치, idx번째 램프의 정보를 저장하기 위해 vSwitch[0]과 vLamp[0]은 비워둔다.

 

//vSwitch[switch]: switch가 켤 수 있는 램프 목록 저장

vSwitch[0]
vSwitch[1] 0
vSwitch[2] 1 3 5
vSwitch[3] 2
vSwitch[4] 3 4 5
vSwitch[5] 1

 

//vLamp[lamp]: lamp를 켤 수 있는 스위치 개수 저장

0 2 1 2 1 2

 

각 스위치를 순회하면서 하나씩 꺼보자. 각 스위치가 끌 수 있는 램프는 vSwitch[i][j] 이므로, vLamp[vSwitch[i][j]]의 수를 1씩 감소시킨다. 만약 각 스위치가 끌 수 있는 램프를 모두 껐음에도 불구하고 vLamp의 각 원소가 1 이상이라면 모든 램프가 켜져 있는 것이므로 1을 출력한다. 만약 해당 스위치를 껐을 때 모든 램프가 켜져 있지 않으면, 다음 스위치를 테스트 하기 위해 다시 해당 스위치를 켜고 vLamp[vSwitch[i][j]]의 수를 1씩 증가시켜 원상 복귀 시킨다. 

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;

int main() {

    int N, M;
    scanf("%d %d", &N, &M);

    vector<vector<int>> vSwitch(N+1);
    vector<int> vLamp(M+1);
    for (int i=1; i<=N; i++) {
        
        int non;
        scanf("%d", &non);
        for (int j=0; j<non; j++) {
            int on;
            scanf("%d", &on);
            vSwitch[i].push_back(on);
            vLamp[on]++;
        }
    }

    for (int i=1; i<=N; i++) {

        for (int j=0; j<vSwitch[i].size(); j++)
            vLamp[vSwitch[i][j]]--;

        bool isAllOn = true;
        for (int j=1; j<=M; j++)
            if (vLamp[j] < 1)  isAllOn = false;
        
        if (isAllOn == true) {
            printf("1\n");
            return 0;
        }

        for (int j=0; j<vSwitch[i].size(); j++) 
            vLamp[vSwitch[i][j]]++;
    }
    printf("0\n");
    return 0;
}