백준 / 거짓말 / 1043번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 거짓말 / 1043번 (골드 4단계)

문제 사이트: https://www.acmicpc.net/problem/1043

 

문제 설명

---

나의 풀이

# 사람의 수 N과 파티의 수 M
n, m = map(int, input().split())

# 결과값
answer = 0

knows = list(map(int, input().split()))
knows.pop(0)

# 파티의 개수 및 참가자
party = []

# 1번째 원소는 파티 참가자의 사람 수라서 제거
for _ in range(m):
    people = list(map(int, input().split()))
    people.pop(0)
    party.append(people)

# 길이가 긴 사람부터 확인 왜냐하면 길수록 다른 사람이랑 접촉할 확률이 높기 때문이다
party.sort(key=lambda x: len(x), reverse=True)

# 아는 사람들을 미리 조사한다.
for i in range(len(party)):
    for k in range(len(knows)):
        for j in range(len(party[i])):
            if party[i][j] == knows[k]:  # 파티 구성원이 knows에 포함되어 있는지 확인
                knows.extend([person for person in party[i] if person not in knows])  # 새로운 사람 추가

# 파티에 거짓말을 아는 사람이 있으면 바로 종료
for i in party:
    person = True
    for j in i:
        if j in knows:
            person = False
            break
    if person:
        answer += 1

print(answer)

문제 원인

1. knows 리스트 업데이트 방식 문제:
   • 진실을 아는 사람(knows) 리스트가 정확히 갱신되지 않거나 중복으로 갱신될 가능성이 있습니다.
   • 파티마다 순회를 돌며 업데이트하더라도, 다른 파티에서 연결된 사람들까지 모두 고려하지 못할 수 있습니다.
   • 이는 "전염"처럼 다른 파티로 연결된 사람들까지 모두 포함시켜야 하는 문제에서 발생합니다.
2. 파티의 정렬과 처리 순서의 의존성:
   • 파티를 길이에 따라 정렬했지만, 파티 크기와 상관없이 모든 파티가 진실 여부에 따라 독립적으로 처리되어야 합니다.
   • 특정 순서로 인해 진실 여부가 잘못 판정될 가능성이 있습니다.
3. 거짓말 가능 여부 판정 문제:
   • 진실을 아는 사람이 있는 파티는 무조건 제외해야 하지만, 알고 있는 사람들의 연결관계가 충분히 업데이트되지 않으면 잘못된 파티가 포함될 수 있습니다.

# 사람의 수 N과 파티의 수 M
n, m = map(int, input().split())

# 결과값
answer = 0

# 진실을 아는 사람 초기화
knows = set(map(int, input().split()[1:]))

# 파티 정보 저장
party = []
for _ in range(m):
    party.append(set(map(int, input().split()[1:])))

# 진실을 아는 사람 집합 확장
for _ in range(m):  # 최대 M번 반복
    for p in party:
        if knows & p:  # 교집합이 존재하면 진실을 아는 사람들과 연결됨
            knows.update(p)  # 진실을 아는 사람 집합에 추가

# 거짓말이 가능한 파티 개수 계산
for p in party:
    if not (knows & p):  # 교집합이 없으면 진실을 아는 사람이 없음
        answer += 1

print(answer)

이건 knows 배열에서 진실을 아는 사람을 모두 알기 위해 2중 반복문을 사용해서 탐색했다.

---

※ 알아야 할 것

knows & p

위 코드를 사용하면 교집합을 알 수 있다.