문제의 링크: https://www.acmicpc.net/problem/1043
내 코드
def DFS(cur):
whoKnowTruth[cur] = True
for x in graph[cur]:
if not whoKnowTruth[x]: DFS(x)
N,M = map(int, input().split()) # 사람의 수 N과 파티의 수 M
truer = list(map(int, input().split()))
graph = [set() for i in range(N + 1)] # 그래프
party = [] # 파티
for i in range(M):
l = list(map(int, input().split()))
party.append(set(l[1:])) # 파티 저장
graph[l[1]] = graph[l[1]]|set(l[2:]) # l[1]과 나머지 성분들 그래프로 연결
for x in l[2:]:
graph[x].add(l[1]) # 양방향으로 연결
whoKnowTruth = [False]*(N + 1)
for x in truer[1:]: DFS(x) # 진실을 아는 사람들과 연결된 모든 성분들을 진실을 아는 사람으로 변경
count = 0
s = set()
for i in range(1,N + 1):
if whoKnowTruth[i]:
s.add(i) # 진실을 알면 집합 s에 추가
for p in party:
if p.isdisjoint(s):
count += 1 # 파티와 진실을 아는 사람들 사이에 교집합이 없으면 Count에서 + 1
print(count)주의해야 할 점
1. graph[l[1]] = graph[l[1]]|set(l[2:])처럼 객체 자체를 변경시키지 않고 함수를 수행하여 객체를 새로 만들어 그 객체의 레퍼런스를 실행하는 함수들은 위와 같이 대입연산자를 통해 변수에 레퍼런스를 대입해야 함을 잊지 말아야한다.
- 사용된 주요 메소드들의 시간 복잡도:
split : O(n)
|(union) : O(m + n)
(새로운 set에 해싱을 하며 넣기만 하면 끝, 사실상 해싱은 O(1)로 취급)
add : O(1)
append : O(1)
isdisjoint : O(n) -> n개의 성분에 대해 O(1)로 중복 여부 검사만 하면 됨.
따라서 위 코드는
DFS는 O(n + e) : 연결된 모든 정점을 한번씩 방문 edge 하나당 한번씩 검사
여기서 edge는 최대 n^2이므로 간단하게 O(n^2)이라 생각하자.
for문은 O(MN) : 합집합연산, 내부 for문이 O(n)
이므로 M,N이 최대 50인 이 문제는 굉장히 빠르게 해결할 수 있다.
다른 사람 코드
jaehaaheaj님의 코드
https://www.acmicpc.net/source/26608539
n,m=map(int,input().split())
l=list(map(int,input().split()))[1:] # 처음부터 앞의 개수부분은 제거
p=[] # party
# 앞의 원소 개수를 제거한 파티 집합 만들기, 단 튜플로 만듬
# 즉, p에 추가되는건 (파티참가인원 리스트, 1)
for _ in range(m):p.append([list(map(int,input().split()))[1:],1])
for _ in range(50): # 모든 파티에 대해서 이를 검사하는 과정을 50번 반복
(벨만 포드와 같은 원리)
for x in [k for k in p if k[1]]:
# l은 진실을 아는 번호들, x는 파티에 속해 있는 모든 파티
for i in l:
if i in x[0]: # i가 x[0]에 있으면, 즉 파티에 속하면 (진실을 아는 사람이 파티에 속하면)
l=list(set(l+x[0])) # l에 파티에 있는 사람 모두 포함
x[1]=0
print(sum([k[1]for k in p]))in은 모든 iterable객체에 대해 사용가능하다.
이 코드는 시간복잡도가 O(n^3)으로 내 것보다 좋지 않다.
단 변수의 초기화에서 [1:]등을 사용하는 것은 배울 점이다.
rkaxhsals의 코드
https://www.acmicpc.net/source/40933539
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
# *truth 는 함수의 가변 변수와 같다.
_, *truth = map(int, input().split()) # 진실을 말하는 사람들
#파티의 각 성분은 input으로 받아온 문자열을 split하여 int로 바꾼 리스트
party = [list(map(int, input().split()))[1:] for _ in range(M)]
# group은 일단 group[x] = x이다.
group = list(range(N + 1))
for p in party: # 모든 파티에 대하여
x = group[p[0]] # p[0]는 파티의 첫 참가자, x = group[파티의 첫 참가자]
for i in range(1, len(p)): # 파티에 참가한 두번째 참가자들부터 마지막까지
y = group[p[i]] # y는 group[파티참가자 중 한명]
for j in range(1, N + 1): # j는 1부터 N까지
if group[j] == y: # group[j]가 y이면, 즉 파티 참가자이면
group[j] = x # group[j]는 x로
# 즉, 위의 과정은 group[파티의 첫 참가자] 에 파티의 참가자 그룹에 속한 모든 성분들을 모두 파티의 첫참가자가 속한 그룹에 속했다고 바꾸는 것을 의미한다.
truth = {group[x] for x in truth} # truth배열은 이제 진실을 말하는 사람들이 속한 그룹들의 번호로 바뀐다.
party = [{group[x] for x in p} for p in party] # 모든 파티들에 대하여 각 파티 리스트를 그 파티에 에 속한 모든 참가자 x에 대하여 x가 속한 그룹 set으로 바꿈
print(sum(all(t not in p for t in truth) for p in party))
# t는 진실을 말하는 그룹, all(t not in p for t in truth)는 각 리스트의 성분
# t not in p도 리스트의 각 성분인 boolean값, for t in truth
# 모든 boolean값이 True이면 즉, 모든 그룹 t가 p에 속하지 않으면 all(t not in p for t in truth)sms True
# 파이썬 내부적으로 True는 1로 취급