코딩테스트 고득점 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
def generate_graph(adj_matrix):
    rst = dict()
    for src, adjs in enumerate(adj_matrix):
        rst[src] = {i for i, v in enumerate(adjs) if v == 1} - set([src])
    return rst

def dfs(graph, root):
    visited = []
    s = [root]

    while s:
        n = s.pop()
        if n not in visited:
            visited.append(n)
            s += graph[n] - set(visited)
    return set(visited)

def solution(n, computers):
    answer = 0

    graph = generate_graph(computers)
    visiteds = set()
    for root in range(n):
        if root in visiteds:
            continue
        visiteds |= dfs(graph, root)
        answer += 1

    return answer