[백준/python] 16960: 스위치와 램프

문제 보러가기!

닻과매 님이 올리신 백준 문제집을 보고 너무 풀고 싶어져서, 오랜만에 풀었다 ㅎㅎ

정말 접근 아이디어가 재미있었다!

N-1 개의 스위치를 눌러서 모든 램프를 켤 수 있는지 판단해야 했다.
N-1개의 스위치로도 모든 램프를 켤 수 있으려면, 어느 한 스위치에 연결된 램프들은 모두 다른 스위치와 연결되어 있어야 한다는 아이디어가 중요했다 ! 상세한 설명은 주석으로..ㅎㅎ 

# N-1 개의 스위치를 눌러서 모든 램프를 켤 수 있으면?
# 어느 한 스위치에 연결된 램프들은 모두 다른 스위치와 연결되어 있어야 함.
# 그러면 1 출력, 아니면 0 출력

from collections import defaultdict
N,M =map(int,input().split())
lamps_connect_switch = defaultdict(list) # 램프가 key, 그와 연결된 스위치 리스트가 value인 딕셔너리
switch_connect_lamps = {} # 스위치가 key, 그와 연결된 램프 리스트가 value인 딕셔너리
for i in range(N):
    connect = list(map(int,input().split()))
    switch_connect_lamps[i]=connect[1:] # 해당 스위치 인덱스가 key, 그와 연결된 램프들을 리스트로 딕셔너리에 저장
    for j in range(1,connect[0]+1): # 램프를 기준으로(key), 그와 연결된 스위치 인덱스를(value. 리스트 형태로) 저장함
        lamps_connect_switch[connect[j]].append(i + 1) # defaultdict을 사용해서 딕셔너리에 해당 램프 인덱스 key가 없을 때는 새로 key를 만들어줌

def check_connection():
    for i in range(N): #스위치 인덱스 기준으로 쭉 보면서
        connected_lamps = switch_connect_lamps[i] 
        for lamp in connected_lamps: # 이 스위치에 연결된 램프들을 하나씩 쭉 본다.
            if len(lamps_connect_switch[lamp]) > 1: # 램프가 해당 스위치 외에 다른 스위치와 연결되어있으면
                continue
            else: # 그 램프는 해당 스위치에만 연결되어 있음.-> 모든 램프를 켜기 위해서 이 스위치는 꼭 있어야 한다는 것.
                break
        else: # 해당 스위치에 연결된 램프들은 모두, 그 스위치 외에 다른 스위치와 연결되어 있다는 것 !
            return 1 # 그러면 이 스위치는 없어도 모든 램프는 불이 켜지므로 1 !!
    return 0

print(check_connection())