[백준] 16960번 : 스위치와 램프 (C++)

10984번: 내 학점을 구해줘

---

문제)

상도는 N개의 스위치와 M개의 램프를 갖고 있다. 스위치는 램프의 전원을 켤 수 있다. 스위치와 연결된 램프의 개수는 0개 이상이다.

가장 처음에 램프는 모두 꺼져 있다.

스위치를 누르면 램프의 전원이 켜진다. 스위치를 이용해서 램프의 전원을 끌 수는 없다. 예를 들어, 한 램프에 두 스위치가 연결되어 있는 경우에 한 스위치를 누르거나, 두 스위치를 모두 누르면 램프는 켜져 있는 상태가 된다.

N개의 스위치를 모두 누르면 모든 램프가 켜진다. 상도는 N-1개의 스위치를 눌러도 모든 램프가 켜지는지 궁금해졌다. 

스위치와 램프의 연결 상태가 입력으로 주어진다. N-1개의 스위치를 눌러서 모든 램프를 켤 수 있는지 알아보자.

 

 

 

입력 :

첫째 줄에 스위치의 수 N, 램프의 수 M이 주어진다. 둘째 줄부터 N개의 줄에는 스위치에 대한 정보가 주어진다. 스위치 정보의 첫 번째 정수는 그 스위치와 연결된 램프의 수이고, 이후 연결된 램프의 번호가 공백으로 구분되어져 있다.

스위치와 램프의 번호는 1번부터 시작한다.

N개의 스위치를 모두 누르면 모든 램프가 켜지는 입력만 주어진다.

 

 

 

출력 :

N-1개의 스위치를 눌러서 모든 램프를 켤 수 있으면 1을, 없으면 0을 출력한다.

 

 

 

 

 

풀이)

 

// 16960. 스위치와 램프
#include <iostream>
#include <vector>
 
using namespace std;
 
int n, m;
vector<vector<int>> vec;
int lamp[2010];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
    vec.push_back(vector<int>(0));
 
    int a, b;
    for (int i = 1; i < n + 1; i++)
    {
        cin >> a;
        vector<int> temp;
        for (int j = 0; j < a; j++)
        {
            cin >> b;
            lamp[b]++;
            temp.push_back(b);
        }
        vec.push_back(temp);
    }
 
    for (int i = 1; i < n + 1; i++)
    {
        bool flag = 1;
        for (int j = 0; j < vec[i].size(); j++)
        {
            if (lamp[vec[i][j]] - 1 <= 0)
            {
                flag = 0;
                break;
            }
        }
 
        // n번째 스위치를 확인해봤을 때,
        // 해당 스위치를 안눌러도 모든 램프가 켜져있다면
        // N - 1개의 스위치를 눌러도 모든 램프가 켜진다.
        if (flag)
        {
            cout << 1;
            return 0;
        }
    }
 
    cout << 0;
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/16960 

16960번: 스위치와 램프