[DFS, BFS] 백준 1043번: 거짓말 / 골드 4

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

1043번: 거짓말

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게

www.acmicpc.net

import collections
n, m = map(int, input().split())

graph = collections.defaultdict(list)
p = list(map(int, input().split()))  # second line
if p[0] == 0:
    print(m)
    quit()

for i in range(1, p[0]):
    graph[p[i]].append(p[i+1])
    graph[p[i+1]].append(p[i])

party = []
for _ in range(m):
    line = list(map(int, input().split()))
    party.append(line)
    if line[0] > 1:
        for i in range(1, line[0]):
            graph[line[i]].append(line[i+1])
            graph[line[i+1]].append(line[i])

known_list = [p[1]]
q = [p[1]]
while q:
    elem = q.pop()
    for next in graph[elem]:
        if next not in known_list:
            q.append(next)
            known_list.append(next)

trash_talk = 0
for i in range(m):
    if party[i][1] not in known_list:
        trash_talk += 1
print(trash_talk)

풀이 속도를 높이는 게 관건이다.

50분이 걸린 이유:

문제 유형을 바로 파악하지 못했다 -> 그래프 문제임을 빨리 파악해야 함

사소한 인덱스 문제 -> 머리로 생각하지 말고 적으면서 하자..