[백준 16960번] 파이썬 - 스위치와 램프

백준 16960 - 스위치와 램프

시간 제한 2초, 메모리 제한 512MB

# 조건

• 상도는 N개의 스위치와 M개의 램프를 갖고 있다.
• 스위치는 램프의 전원을 켤 수 있다.
• 스위치와 연결된 램프의 개수는 0개 이상이다.
• 가장 처음에 램프는 모두 꺼져 있다.
• 스위치를 누르면 램프의 전원이 켜진다.
• 스위치를 이용해서 램프의 전원을 끌 수는 없다.
  • 예를 들어, 한 램프에 두 스위치가 연결되어 있는 경우에 한 스위치를 누르거나, 두 스위치를 모두 누르면 램프는 켜져 있는 상태가 된다.
• N개의 스위치를 모두 누르면 모든 램프가 켜진다.
• 상도는 N-1개의 스위치를 눌러도 모든 램프가 켜지는지 궁금해졌다.
• 스위치와 램프의 연결 상태가 입력으로 주어진다.
• N-1개의 스위치를 눌러서 모든 램프를 켤 수 있는지 알아보자.

입력

• 첫째 줄에 스위치의 수 N, 램프의 수 M이 주어진다.
• 둘째 줄부터 N개의 줄에는 스위치에 대한 정보가 주어진다.
• 스위치 정보의 첫 번째 정수는 그 스위치와 연결된 램프의 수이고, 이후 연결된 램프의 번호가 공백으로 구분되어져 있다.
• 스위치와 램프의 번호는 1번부터 시작한다.
• N개의 스위치를 모두 누르면 모든 램프가 켜지는 입력만 주어진다.

출력

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

# 제한

• 1<=N, M<=2,000

# 접근 방법

• 각 스위치가 켤 수 있는 램프의 번호를 입력받는다.
• 처음에 58%에 틀렸습니다를 받은 아이디어는 아래와 같았다.
  • 이후, 켤 수 있는 램프의 수가 많은 스위치부터 램프를 켜는데,
    • 만약 현재 스위치에서 켤 수 있는 램프가 이미 켜져 있다면 cnt-1을 한 후 넘어간다.
  • 모든 스위치를 순회한 후 모든 램프가 켜져 있고, cnt가 0보다 크다면 1을 출력한다.
  • 이 경우, 1 2 3 4 5를 켜는 스위치와 2 3 4 5 6을 켜는 스위치, 6 7 8을 켜는 스위치가 있다고 가정한다면,
  • 2 3 4 5 6 스위치를 사용하지 않아도 되지만 먼저 키게 되어 0을 출력하는 반례를 찾았다.
• 따라서, 조금 생각을 변형하여 풀어주었다.
  • 각 램프를 켤 수 있는 스위치의 수를 기록해주었다.
  • 각 스위치를 순회하며 켤 수 있는 램프의 카운트 -1 이 0이라면 break
  • 해당 램프들의 수가 1이상이라면, 해당 스위치를 사용하지 않고도 켤 수 있으므로 1을 출력해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N, M = map(int, input().split())  
lamp = [0] * (M+1)  
switch = [[]]  
lamp[0] = 1  
for i in range(N):  
    order = list(map(int, input().split()))  
    switch.append(order[1:])  
    for j in order[1:]:  
        lamp[j] += 1  

if 0 in lamp:  
    print(0)  
else:  
    for i in switch[1:]:  
        for j in i:  
            if lamp[j] - 1 == 0:  
                break  
        else:  
            print(1)  
            break  
    else:  
        print(0)