코딩테스트 고득점 Kit - 그래프 2 (Level 3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
from collections import defaultdict
from queue import deque

# w - i
def bfs(graph, src):
    visited = []
    q = deque([src])

    while q:
        v = q.popleft()
        if v not in visited:
            visited.append(v)
            q += graph[v] - set(visited)
    return visited

def solution(n, results):
    answer = 0

    graph = {v: set() for v in range(1, n+1)}
    for v1, v2 in results:
        graph[v1].add(v2)
    visited = {}
    for v in graph:
        visited[v] = bfs(graph, v)


    graph = {v: set() for v in range(1, n+1)}
    for v1, v2 in results:
        graph[v2].add(v1)
    inv_visited = {}
    for v in graph:
        inv_visited[v] = bfs(graph, v)

    answer = 0
    for v in graph:
        n_knowns = len(set(visited[v] + inv_visited[v]))
        if n_knowns == n:
            answer += 1

    return answer