[Seop's의 코드풀이] 백준 1043 거짓말 - Python

www.acmicpc.net/problem/1043

1043번: 거짓말

문제 요약

진실을 알고있는 사람과 연관된 파티에서는 거짓말을 하지 못한다. 즉 진실을 알고 있는 사람과 연관되어 있지 않은 그룹이

몇 개 있는지 파악해야 하는 문제이다.  

문제의 예제 입력으로는 문제 파악이 힘들 수 있기 때문에 아래 예시를 함께 봐보자!   

 

입력
4 3
1 4
2 1 2
1 3
2 4 3

4명의 사람과 3개의 파티가 존재한다.

진실을 알고 있는 사람은 1명이며 4번이 진실을 알고 있다.

위의 예시에서 4번 사람은 3번 파티에 참가하고 있다.

3번 파티에는 3번 사람이 함께 참가하고 있어 3번도 진실을 알 수 있다.

그러므로 3번 사람이 참가하고 있는 2번 파티에서도 거짓말을 하면 안된다.

즉 거짓말을 할 수 있는 파티는 1번파티 밖에 없다.

 

문제풀이 IDEA

문제풀이의 IDEA는 생각보다 간단하다. 위의 예시를 그대로 적용하면 된다.

1. 진실을 알고 있는 사람을 stack에 추가한다.
2. stack을 왼쪽에서 pop을 진행하여 해당 사람이 참가하고 있는 파티에서는 거짓말을 할 수 없다고 표시한다.
3. 파티에 참여하고 있는 인원을 stack에 추가한다.
4. stack이 빈 상태가 될때 까지 2~3번을 반복한다.
5. 거짓말을 할 수 있는 파티의 수를 체크하여 정답으로 반환한다. 

즉 진실과 연관되어 있는 사람들의 파티는 모두 거짓말을 할 수 없다고 체크하면 된다.

이때 체크한 파티나 인원은 또 체크하지 않도록 하는 것이 중요하다.(무한 루프에 빠질 수 있다.)

 

전체적인 코드는 다음과 같다. 

질문과 피드백은 언제나 감사드립니다. 

import sys
from collections import deque
input = sys.stdin.readline

class Soluction :
    def __init__(self, N,M) :
        self.N = N
        self.M = M

        self.personDict = dict()
        self.partyDict = dict()
        self.partyPerson = dict()

        self.check = [True]*(N+1)
        self.stack = deque([])
    
    def initData(self) :
        for i in range(1,self.N+1) :
            self.personDict[i] = set()
        for i in range(1, self.M + 1) :
            self.partyDict[i] = True
            self.partyPerson[i] = []
        
        knows = list(map(int, input().split(" ")))
        for k in range(1, len(knows)) :
            self.stack.append(knows[k])
        
        for i in range(1, self.M+1) :
            party = list(map(int, input().split(" ")))
            for j in range(1,party[0]+1) :
                self.personDict[party[j]].add(i)
                self.partyPerson[i].append(party[j])
    
    def checkParty(self) :
        while(self.stack) :
            temp = self.stack.popleft()
            if self.check[temp] :
                self.check[temp] = False
                for k in self.personDict[temp] :
                    self.partyDict[k] = False
                    for c in self.partyPerson[k] :
                        if self.check[c] :
                            self.stack.append(c)
    
    def getAnswer(self) :
        self.initData()
        self.checkParty()
        answer = 0 
        for k,v in self.partyDict.items() :
            if v :
                answer += 1
        return answer



if __name__ == "__main__":
    N, M = map(int, input().split(" "))
    s = Soluction(N,M)
    answer = s.getAnswer()
    print(answer)