[Silver IV] 스위치와 램프 - 16960

문제 링크

성능 요약

메모리: 122052 KB, 시간: 400 ms

분류

구현, 브루트포스 알고리즘

제출 일자

2025년 5월 27일 21:39:32

문제 설명

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

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

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

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

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

입력

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

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

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

출력

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

---

💡 해결 방법

💻 코드

# https://www.acmicpc.net/problem/16960
 
from sys import stdin
input = stdin.readline
 
from itertools import combinations
 
n, m = map(int, input().split())
 
sw = dict()
 
for x in range(n):
    temp = list(map(int, input().split()))
    sw[x] = tuple(temp[1:])
 
 
target = set(x for x in range(1, m+1))
 
 
for nowsw in combinations(sw.values(), n - 1):
    now = set()
    for x in nowsw:
        now.update(x)
    
 
    if now == target:
        print(1)
        exit()
 
 
 
 
 
print(0)