[백준] 1043번 거짓말 _ Python

[초기 접근 방법]

- 맨 처음에 제시한 사람은 무조건 "진실"만을 들어야 한다.
- 각 사람마다 일관되게 "과장된 이야기 or 진실"을 들어야 한다.
- 해당 파티에서는 무조건 "과장된 이야기 or 진실"을 이야기해야 한다.

1. 제시한 사람이 있는 파티는 일단 전부 진실을 말한다.
2. 위 파티에 있는 사람들 모두 "진실파티" 에 넣는다.
3. 각 파티를 탐색하면서 파티 참석 인원 중
    "진실파티"에 있는 사람이 있다면 참가한 사람들을 "진실파티"에 추가를 하고, 파티를 처음부터 다시 탐색해야 한다.
    "진실파티"에 있는 사람이 없다면 해당 루프에서 종료한다.

 

 

 

[생각]

1. input.split() 내에서의 슬라이싱

set(map(int, input().split()[1:]))

 

 

2. set.union()

 

list의 extend() 처럼 두 set 을 합집합 할 수 있다.

knowList = knowList.union(party)

 

 

3. set 연산자

 

| (합집합)

     s1.union(s2)
& (교집합)

     s1.intersection(s2)
- (차집합)

     s1.difference(s2)
^ (합집합-교집합)

     set.symmetric_difference(s1, s2)

 

# party에 knowList 원소가 있는지 판별하는 방법

# 1)
for know in knowList:
    if know in party:
        cnt1 += 1

# 2)
if knowList & party:
    cnt2 += 1

 

 

+. 이외에도 각 파티의 참가 인원들을 노드로 연결지어 그래프 탐색으로 풀 수도 있다.

 

 

[코드]

1. for 문으로 일일이 knowList를 갱신하는 코드

# 구현

# 풀이 시간 : 30분
# 시간복잡도 : O(M * a)
# 공간복잡도 : O(M or N)
# 참고 : -

import sys
input = sys.stdin.readline

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

# 진실을 아는 사람의 수, 번호가 주어짐
knowList = list(map(int, input().split()))
knowList.remove(knowList[0])
knowList = set(knowList)

# 각 파티에 오는 사람의 수, 번호
partyList = [list(map(int, input().split())) for _ in range(M)]

# 각 파티에서 거짓말을 할 수 있는지를 체크할 수 있는 리스트
# True : 거짓말 가능 / False : 진실만을 말함
visitedLie = [False] * M

while True:
    knowListLength = len(knowList)

    # 모든 파티 탐색
    for i in range(M):
        addTrue = False
        # 각 파티에 "진실 파티원"이 있는지 탐색
        for j in range(1, len(partyList[i])):
            # "진실 파티원"이 있을 경우 "진실파티"에 추가
            if partyList[i][j] in knowList:
                for k in range(1, len(partyList[i])):
                    knowList.add(partyList[i][k])
                addTrue = True
                break

        # 추가되었음을 flag → 해당 파티에서는 진실만을 말해야한다.
        if addTrue:
            visitedLie[i] = False

        # "진실 파티원"이 없기 때문에 해당 파티에서는 거짓말을 말해도 된다.
        else:
            visitedLie[i] = True

    # 모든 파티를 탐색했음에도 더 이상 "진실파티"가 갱신이 되지 않는 경우 탐색을 종료한다.
    if knowListLength == len(knowList):
        break


# 거짓말을 해도 되는 파티 개수를 출력한다.
result = 0
for i in range(M):
    if visitedLie[i]:
        result += 1

print(result)

 

 

 

2. & 연산자와 flag 없이 간결히 한 코드

import sys
input = sys.stdin.readline

# 사람의 수, 파티의 수
N, M = map(int, input().split())
# 진실을 아는 사람의 수, 번호가 주어짐
knowList = set(map(int, input().split()[1:]))
# 각 파티에 오는 사람의 수, 번호
partyList = [set(map(int, input().split()[1:])) for _ in range(M)]

for _ in range(M):
    for party in partyList:
        # 파티 참석자 중에 진실을 알고 있는 사람이 있다면
        if knowList & party:
            knowList = knowList.union(party)

trueParty = 0
for party in partyList:
    for know in knowList:
        if know in party:
            trueParty += 1
            break

print(M - trueParty)

 

 

 

3. 최적화 1+2

import sys
input = sys.stdin.readline

# 사람의 수, 파티의 수
N, M = map(int, input().split())
# 진실을 아는 사람의 수, 번호가 주어짐
knowList = set(map(int, input().split()[1:]))
# 각 파티에 오는 사람의 수, 번호
partyList = [set(map(int, input().split()[1:])) for _ in range(M)]

for _ in range(M):
    knowListLength = len(knowList)

    for party in partyList:
        # 파티 참석자 중에 진실을 알고 있는 사람이 있다면
        if knowList & party:
            knowList = knowList.union(party)

    # 모든 파티를 탐색했음에도 더 이상 "진실파티"가 갱신이 되지 않는 경우 탐색을 종료한다.
    if knowListLength == len(knowList):
        break

trueParty = 0
for party in partyList:
    for know in knowList:
        if know in party:
            trueParty += 1
            break

print(M - trueParty)

 

 

 

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