16960 스위치와 램프

문제

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

16960번: 스위치와 램프

 

접근

• N개의 스위치마다 해당 스위치를 누르지 않았을 때 M개의 모든 램프를 켤 수 있는지 확인한다.
• 한 스위치에 M개의 램프가 연결된 경우에는 항상 N-1개의 스위치로 모든 램프를 켤 수 있기 때문에, 실제 시간 복잡도는 이론상 계산한 O(N^2 * M) 보다 훨씬 작을 것이다.

 

풀이

• 각 스위치에 연결된 램프를 저장하기 위해 딕셔너리 사용
• 각 스위치를 누르지 않았을 때 N-1개의 스위치로 모든 램프를 켤 수 있는지 check 배열로 확인

n, m = map(int, input().split())

connect = dict()
for i in range(1, n + 1):
    k, *num = map(int, input().split())
    connect[i] = num

for i in range(1, n + 1):
    check = [False] * (m + 1)
    for j in range(1, n + 1):
        if i == j:
            continue

        for x in connect[j]:
            check[x] = True

    if sum(check) == m:
        print(1)
        break
else:
    print(0)