[Python] 백준 1043번: 거짓말 - bfs, graph

문제

1043번: 거짓말

문제

파티에 있는 사람들을 저장하는 파티 리스트를 만들고,

또 같은파티에 있는 사람들을 저장하기위해 인접리스트를 사용했다.

 

처음부터 진실을 알고있는 사람을 큐에 다 저장 한 후, bfs방식으로 인접리스트를 돌며 

새로 소식을 접한 사람은 진실을 들었는지 여부를 저장하는 heard배열에 저장해줬다.  

 

그 후, 파티리스트를 돌며 heard배열에 있는 사람이 한명이라도 포함된 파티는 break을 해줬고,

한명도 포함되지 않은 경우만 count를 늘려갔다. 마지막에 count를 프린트해줬음

import sys
from itertools import combinations
from collections import deque

# N: 사람수 / M: 파티 수
N, M = map(int, sys.stdin.readline().split(" "))

# 인접리스트
adj = [[] for _ in range(N)]
parties = []

# 진실을 아는 사람
know = list(map(int, sys.stdin.readline().split(" ")))
heard = [0 for _ in range(N)]

# 한명도 모르면
if know[0] == 0:
    # 파티 개수 출력
    print(M)
else:
    # 맨 앞값(인원 정보) 삭제
    know.pop(0)

    # 인접리스트에 추가, 파티리스트에 인원 넣기
    for _ in range(M):
        party = list(map(int, sys.stdin.readline().split(" ")))
        if party[0] == 0:
            parties.append(["none"])
        else:
            parties.append(party[1:])

            # 혼자가 아닌 경우 조합으로 둘씩 짝지어줌 -> 인접리스트에 넣기
            if party[0] != 1:
                com = combinations(party[1:], 2)
                for each in com:
                    adj[each[0]-1].append(each[1] - 1)
                    adj[each[1]-1].append(each[0] - 1)

    # 큐에 아는사람 다 넣기
    queue = deque()
    for each in know:
        queue.append(each-1)
        heard[each-1] = 1

    # bfs로 인접리스트 탐색
    while queue:
        now = queue.popleft()
        for one in adj[now]:
            if heard[one] == 0:
                heard[one] = 1
                queue.append(one)

    heardperson = []
    for i in range(len(heard)):
        if heard[i] == 1:  # 들은애
            heardperson.append(i+1)

    count = 0
    for party in parties:
        flag = 0
        for each in heardperson:
            if each in party:
                flag = 1
                break
        if flag == 0:
            count += 1

    print(count)

 

문제 자체는 어렵지 않다고 생각했는데 테스트케이스가 많이 주어지지 않아서 구멍을 찾는게 힘들었던 문제.

다른분들이 찾아둔 반례에서 원인을 발견했다. 원인은 플래그를 초기화해주지 않은 실수였다 ㅠㅠ

 

 

TC1

4 4
1 1
2 1 2
1 3
2 3 4
0 0
(답 3)

 

TC2
4 4
1 1
2 3 2
3 4 1 3
2 4 1
0 0
(답 1)

 

TC3
3 2
1 1
2 2 3
2 1 2
(답 0)