백준 1043 [거짓말] 파이썬

https://www.acmicpc.net/problem/1043

 

# 백준 1043 거짓말
import sys
from collections import deque
input = sys.stdin.readline

# N: 사람 수, M: 파티 수
N, M = map(int, input().split())

# 진실을 아는 사람 목록
knowns = list(map(int, input().split()))
knowns_num = knowns.pop(0)  # 첫 번째 숫자는 진실을 아는 사람 수
ans = 0  # 거짓말할 수 있는 파티 수

# 진실을 아는 사람을 표시하는 배열
knows = [False for _ in range(N+1)]  # 인덱스 1~N 사용

# 진실을 아는 사람들 체크
for known in knowns:
    knows[known] = True

# 사람들 간의 연결 관계를 저장할 그래프 (진실을 아는 사람과 연결된 사람은 모두 진실을 알게 됨)
graph = [[] for _ in range(N+1)]

# 각 파티에 참석한 사람들 정보 저장
partys = []
for i in range(M):
    participation = list(map(int, input().split()))
    participation_num = participation.pop(0)  # 첫 번째 숫자는 참석자 수
    partys.append(participation)

    # 파티에 참석한 사람들끼리 서로 연결시켜 줌 (양방향 연결)
    for j in range(participation_num):
        for k in range(j+1, participation_num):
            graph[participation[j]].append(participation[k])
            graph[participation[k]].append(participation[j])

# BFS를 통해 진실을 아는 사람과 연결된 모든 사람을 진실을 아는 사람으로 확장
for party in partys:
    for p in party:
        if knows[p]:  # 만약 이 파티에 진실을 아는 사람이 있다면
            q = deque()
            q.append(p)
            while q:
                p_num = q.popleft()
                for next_p_num in graph[p_num]:
                    if not knows[next_p_num]:  # 아직 진실을 모르는 사람이라면
                        knows[next_p_num] = True
                        q.append(next_p_num)

# 이제 각 파티에서 진실을 아는 사람이 하나도 없다면, 거짓말 가능
for party in partys:
    can_speak = True
    for p in party:
        if knows[p]:  # 진실을 아는 사람이 있다면
            can_speak = False
            break
    if can_speak:
        ans += 1

# 거짓말할 수 있는 파티의 수 출력
print(ans)

맞추긴했는데, BFS를 두 번 돌렸다. (비효율적)

 

GPT가 개선한 코드를 알려주어 첨부한다.

# 백준 1043 거짓말 - 개선 버전
import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
knowns = list(map(int, input().split()))
knowns_num = knowns.pop(0)

truth_known = [False] * (N + 1)

for person in knowns:
    truth_known[person] = True

graph = [[] for _ in range(N + 1)]
parties = []

for _ in range(M):
    participants = list(map(int, input().split()))
    participants.pop(0)
    parties.append(participants)
    
    # 양방향 연결
    for i in range(len(participants)):
        for j in range(i + 1, len(participants)):
            graph[participants[i]].append(participants[j])
            graph[participants[j]].append(participants[i])

# 진실 아는 사람들 전체 확장 (BFS 1번만)
q = deque()
for i in range(1, N + 1):
    if truth_known[i]:
        q.append(i)

while q:
    current = q.popleft()
    for neighbor in graph[current]:
        if not truth_known[neighbor]:
            truth_known[neighbor] = True
            q.append(neighbor)

# 진실을 모르는 사람만 있는 파티만 카운트
ans = 0
for party in parties:
    if all(not truth_known[p] for p in party):
        ans += 1

print(ans)