거짓말 (1043번) - 백준 (BOJ)

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

1043번: 거짓말

 

백준 - 거짓말 (1043번)

 

난이도 : Gold 4

알고리즘 : DFS (Graph)

풀이 소요 시간 : 40분

Time Complexity : O( 파티 참석 인원수 총 합? )

 

import sys
input = sys.stdin.readline


if __name__ == '__main__':
    N, M = map(int, input().split())
    truth = [False] * (N+1)
    # 1
    _, *stack = map(int, input().split())
    # 2
    for i in stack:
        truth[i] = True
    
    pps = [[] for _ in range(N+1)]
    ps = []
    for i in range(M):
        _, *party = map(int, input().split())
        ps.append(party)
        # 3
        for p in party:
            pps[p].append(i)
    
    # 4
    while stack:
        p = stack.pop()
        for pi in pps[p]:
            for p in ps[pi]:
                if truth[p]:
                    continue
                truth[p] = True
                stack.append(p)
    
    # 5
    print(sum(0 if any(truth[p] for p in party) else 1 for party in ps))

 

DFS로 해결 가능한 문제였다.

 

 

# 1. 초기에 진실을 알고 있는 사람들로 stack을 구성한다.

 

# 2. 진실을 알고 있는 사람들을 truth에 True로 기록한다.

 

# 3. 특정 인원이 속한 파티의 번호를 pps에 기록한다.

 

# 4. DFS를 진행하면서

진실을 알고 있는 인원과 같이 파티에 참석한 인원들은 truth에 True로 기록하고

stack에 추가한다.

 

# 5. 진실을 아는 사람이 아무도 없는 party 개수가 정답