백준 - 1043번(그래프)

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

1043번: 거짓말

import sys
from collections import deque

def TrueOrFalse(ans):
    n, m = map(int, sys.stdin.readline().split())

    known = deque(list(map(int, sys.stdin.readline().split())))
    known.popleft()

    check = [False for _ in range(n + 1)]
    party = []
    relation = [[] for _ in range(n + 1)]

    for i in known: #처음에 주어지는 거짓말을 미리 아는 사람들
        check[i] = True

    for i in range(m): #파티에 참석하는 사람들과 사람들관의 관계
        arr = deque(list(map(int, sys.stdin.readline().split())))
        x = arr.popleft()
        for j in arr:
            for t in arr:
                relation[j].append(t) #사람들관의 관계
        party.append(arr) #파티에 참석하는 사람 목록

    q = deque([])
    for i in range(1, n + 1):
        if check[i] == True:
            q.append(i) #처음부터 진실을 알고 있던 사람들을 우선 q에 넣어줌

    while q: #BFS를 이용해서 연쇄적으로 탐색
        a = q.popleft()
        for i in relation[a]:
            if check[i] == False:
                check[i] = True
                q.append(i)

    for i in party: #최종적으로 나온 check 배열을 바탕으로 파티를 열 수 있는지 확인
        ck = 0
        for j in i:
            if check[j] == True:
                ck = 1
                break
        if ck == 0:
            ans = ans + 1

    return ans

print(TrueOrFalse(0))

 

먼저 check 배열로 진실을 알고 있는 사람은 True 아닌 사람은 False로 한다.
party 배열에는 각 파티에 참여하는 사람들의 정보를 담고 있다.
relation 배열은 n이라는 사람이 거짓말을 알 때 함께 알게 되는 사람들의 정보를 담고 있다.

 

핵심 아이디어는 먼저 초대장에 올 사람들을 한번 다 훑는 것이다.
그게 relation 배열을 만든느 과정이다. 따라서 처음에 진실을 알고 있는 사람들을 시작으로 while문을 이용해 bfs를 사용해서 relation의 정보를 바탕으로 탐색하면 해당 사람이 존재할 경우 check 가 True로 바뀐다. 해당 while문이 모두 종료되고 나면 최종적으로 진실을 아는 사람과 그렇지 않은 사람이 구분된다. party의 원소로 반복문을 실행해 party에 참석하는 사람 중 진실을 아는 사람이 1명이라도 있으면 그 파티는 열 수 없고 그렇지 않으면 ans에 1을 추가해준다.