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

백준의 스위치와 램프(16960) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 먼저 본인이 사용한 핵심 변수 2개 부터 설명하겠다.

   하나는 각 스위치별로 연결되어 있는 램프를 저장해놓은 Vector와, 램프에 연결된 스위치의 갯수를 저장해 놓았다.

   Vector는 Switch[a] = { 1, 2 } 이런식으로 벡터 배열식으로 선언하였는데 이것이 의미하는 것은

   "a번 스위치에 연결된 램프는 1번, 2번 램프가 있습니다." 를 의미하고,

   Lamp[a] = b 라는 배열의 의미는 "a번 램프에 연결된 스위치의 갯수는 b개입니다." 를 의미한다.

  

2) 이제부터 본격적인 구현에 들어가보자.

   1번부터 N번 스위치까지 모두 하나씩 꺼보는 것이다. 끌 때, 하는일이 무엇이냐 ?! Lamp[] 배열에 저장되어 있는

   갯수를 줄여나가면 된다. 이게 무슨 말일까??

   예를 들어서 1번 스위치에서 1, 2번 램프가, 2번 스위치에서 1,2,3번 램프가 연결되어 있다고 가정해보자.

   역시 말보다는 그림이다.

  

    이런 그림인 상태이다. 그럼, 위에서 말했던 2개의 핵심 변수들의 상태부터 알아보자.

    아마 스위치에 연결된 램프들의 번호를 넣어놓은 벡터는 다음과 같을 것이다.

    Switch[1] = { 1, 2 } ; Switch[2] = { 1, 2, 3 }

    그리고, 램프에 연결된 스위치의 갯수를 저장해둔 배열은 다음과 같을 것이다.

    Lamp[1] = 2 ; Lamp[2] = 2 ; Lamp[3] = 1

    이 때, 1번 스위치를 끄게 되면 어떻게 될까?? 아마 램프에 연결된 스위치의 갯수를 저장해둔 배열이 다음과 같아질 것이다.

    Lamp[1] = 1; Lamp[2] = 1; Lamp[3] = 1

    그럼 ?? 답은 1이다. 왜 ?? 스위치가 여러개 연결되어 있는 램프의 경우, 하나의 스위치만 키더라도 램프를 켤 수 있기 때문

    에, 하나의 스위치를 껐음에도 모든 램프에 연결된 스위치가 1개 이상 있다는 얘기이고 이 말은 하나의 스위치를 끄더라도

    모든 램프에 불을 켤 수 있다는 것을 의미하게 되기 때문이다.

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 2000 + 1
using namespace std;
 
int Lamp[MAX];
int N, M;
vector<int> Switch[MAX];
 
void Input()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        int a; cin >> a;
        for (int j = 0; j < a; j++)
        {
            int b; cin >> b;
            Switch[i].push_back(b);
            Lamp[b]++;
        }
    }
}
 
bool Switch_Power_Off(int Idx)
{
    bool Flag = true;
    for (int i = 0; i < Switch[Idx].size(); i++)
    {
        int x = Switch[Idx][i];
        Lamp[x]--;
 
        if (Lamp[x] <= 0)
        {
            Flag = false;
        }
    }
 
    for (int i = 0; i < Switch[Idx].size(); i++)
    {
        int x = Switch[Idx][i];
        Lamp[x]++;
    }
 
    return Flag;
}
 
void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        if (Switch_Power_Off(i) == true)
        {
            cout << 1 << endl;
            return;
        }
    }
    cout << 0 << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}