문제 바로가기
문제:
상도는 N개의 스위치와 M개의 램프를 갖고 있다. 스위치는 램프의 전원을 켤 수 있다. 스위치와 연결된 램프의 개수는 0개 이상이다. 가장 처음에 램프는 모두 꺼져 있다. 스위치를 누르면 램프의 전원이 켜진다. 스위치를 이용해서 램프의 전원을 끌 수는 없다. 예를 들어, 한 램프에 두 스위치가 연결되어 있는 경우에 한 스위치를 누르거나, 두 스위치를 모두 누르면 램프는 켜져 있는 상태가 된다. N개의 스위치를 모두 누르면 모든 램프가 켜진다. 상도는 N-1개의 스위치를 눌러도 모든 램프가 켜지는지 궁금해졌다. 스위치와 램프의 연결 상태가 입력으로 주어진다. N-1개의 스위치를 눌러서 모든 램프를 켤 수 있는지 알아보자.
입력:
첫째 줄에 스위치의 수 N, 램프의 수 M이 주어진다. 둘째 줄부터 N개의 줄에는 스위치에 대한 정보가 주어진다. 스위치 정보의 첫 번째 정수는 그 스위치와 연결된 램프의 수이고, 이후 연결된 램프의 번호가 공백으로 구분되어져 있다. 스위치와 램프의 번호는 1번부터 시작한다. N개의 스위치를 모두 누르면 모든 램프가 켜지는 입력만 주어진다.
출력:
N-1개의 스위치를 눌러서 모든 램프를 켤 수 있으면 1을, 없으면 0을 출력한다.
풀이:
import sys
from itertools import combinations
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n, m = map(int,sys.stdin.readline().split(" "))
graph = [[] for _ in range(n)]
for i in range(n):
lst = list(map(int,sys.stdin.readline().split(" ")))
for j in lst[1::]:
graph[i-1].append(j)
x = list(combinations(graph,n-1))
flag = False
for i in x:
a = sum(i,[])
if len(set(a)) >= m:
flag = True
print(1 if flag else 0)
아이디어는 단순하게 n-1 개로 m개의 리모컨을 켤 수 있는지 없는지 확인하는것이라
이차원 그래프로 각 스위치마다 연결된 전등들을 담아둔다.
그리고 그 그래프를 n-1개 조합으로 만들어준다.
그렇게 나온 램프들을 set으로 만들어 갯수가 m개가 되면
n-1개로 가능하므로 flag 를 True로 만들어준다.
그렇지 않으면 기본 셋팅인 False로 바꿔준다.
댓글