Notice
Recent Posts
Recent Comments
Link
나의 개발일지
[백준] 1043 거짓말 [Python, 파이썬] 본문
- 문제 : https://www.acmicpc.net/problem/1043
- 🔑 union, find [유니온 파인드]
- 진실을 아는 사람들을 모두 같은 번호로 묶어준다. union
- 각 파티마다 오는 사람들을 모두 같은 번호로 묶어준다. union
- 진실을 아는 사람들이 오는 파티면 1번 과정에서의 그룹에 포함된다.
- 진실을 아는 사람들의 그룹과, 각 파티의 그룹이 겹치지 않으면 거짓말을 한다. find
- 거짓말할 수 있는 파티의 개수를 세면 끝 ✨
- 예외로 진실을 아는 사람이 없으면 파티의 횟수를 출력하고 종료했다.
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
parent = [i for i in range(n+1)]
true = list(map(int, input().split())) # 진실을 아는 사람 수, 번호
partys = [list(map(int, input().split())) for _ in range(m)]
def union(a, b):
x = find(a)
y = find(b)
parent[y] = x
def find(x):
if parent[x] == x:
return parent[x]
parent[x] = find(parent[x])
return parent[x]
if true[0] == 0: # 진실을 아는 사람이 없으면 모든 파티에서 거짓말 가능
print(m)
exit()
for i in range(2, len(true)): # 진실을 아는 사람 union
union(true[1], true[i])
for party in partys: # 파티마다 사람들 union
for i in range(2, len(party)):
union(party[1], party[i])
answer = 0
x = find(true[1])
for party in partys:
if find(party[1]) != x:
answer += 1
print(answer)
'백준' 카테고리의 다른 글
[백준] 1765 닭싸움 팀 정하기 [Python, 파이썬] (0) | 2024.01.17 |
---|---|
[백준] 1541 잃어버린 괄호 [Python, 파이썬] (0) | 2024.01.10 |
[백준] 2307 도로검문 [Python, 파이썬] (1) | 2024.01.09 |
[백준] 1202 보석 도둑 [Python, 파이썬] (0) | 2024.01.05 |
[백준] 1874 스택 수열 [Python, 파이썬] (0) | 2024.01.05 |
Comments