백준 3018번
https://www.acmicpc.net/problem/3018

문제

후기

⏰ 풀이시간 1시간30분 ++⏰

이 문제가 정말 실버4 문제가 맞나 싶은 난이도의 문제였다.

구현하기 어려운 부분이 있었다기 보다는, 문제의 설명을 이해하는 것이 까다로웠다.

문제에서 요구하는 바를 요약하자면,

1. 어떠한 새로운 노래를 부를 수 있는것은 선영이뿐이다.
2. 선영이가 캠프파이어에 참가하지 않으면, 나머지 참석자들은 서로가 알고있는 선영이의 노래를 공유한다.
3. 선영이를 포함해, 선영이가 불렀던 모든 노래를 알고 있는 참석자들을 오름차순으로 출력한다.

예제 입력 1을 예시로 들어보자.

2 1 2 에서는 1(선영) , 2가 캠프파이어에 참여했다. 선영이가 A라는 노래를 알려줬다고 해보자

그러면 현재까지는 1은 A, 2는 A 노래를 알고있다.

3 2 3 4 에서는 1(선영)이가 캠프파이어에 참여하지 않았다. 이러면, 참석자들은 서로 알고있는

선영이의 노래를 공유하는데, 2가 선영이의 A 노래를 알고 있으므로, 3과 4에게 공유해주게 된다.

그러면 현재까지는 1은 A , 2는 A , 3은 A , 4는 A의 노래를 알고있다.

3 4 2 1 에서는 선영이가 B라는 노래를 부르게 된다.

결과적으로

1: A,B
2: A,B
3: A
4: A,B
의 노래를 알고있으므로 1,2,4를 출력하는것이 정답이 된다.

선영이가 참석할 때 마다 부르는 노래의 Key값을 다르게 해서, 모든 key 안에 들어가있는

value를 찾아내서 출력하는 식으로 구현하게 되었다.

나의 풀이

import sys
input =sys.stdin.readline
from collections import defaultdict

N = int(input())
E = int(input())
li = defaultdict(set)
cnt = 0

for _ in range(E):
  group = list(map(int,input().split()))
  group = group[1:] #0번째 인덱스는 참여자 수이므로 슬라이싱해준다.
  if 1 in group: #선영이가 참석했으면
    for i in group: # cnt 라는 노래를 현재 그룹원들은 모두 알게된다.
      li[cnt].add(int(i))
    cnt +=1 #다음 노래는 달라져야 하므로 cnt의 값을 증가

  else: #선영이가 참석하지 않았으면
    for i in range(len(group)): #group안을 돌면서
      for key, values in li.items():
        if group[i] in values: #선영이의 노래를 알고있는 그룹원이 있으면 
          for k in group: #나머지 그룹원들에게 노래를 공유해준다.
            if k not in li[key]:
              li[key].add(k)
result = []
li= dict(li)
for i in range(1, N+1):
  check = 0 #선영이의 노래를 몇곡 알고있는가
  for key,values in li.items():
    if i in values:
      check+=1
  if check == len(li): #모든 노래를 다 알고있으면
    result.append(i) #그 참석자는 결과값에 append 해준다.
result.sort()
  
for i in result:
  print(i)