프로그래머스 3단계 - [네트워크]

https://programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

1. 문제이해

 - BFS 를 활용한 전체 탐색

 - 연결된 묶음 갯수세기

 

2. 코드 작성

def solution(n, computers):
    answer = 0
    
    dict_computer = dict()
    temp = set()

    for i, computer in enumerate(computers):
        dict_computer[i] = [idx for idx, c in enumerate(computer) if c == 1 if idx != i]
    
    for k in dict_computer.keys():
        if k not in temp:
            temp.add(k)
            temp.update(set(bfs(dict_computer, k)))
            answer += 1

    return answer

def bfs(graph, start_node):
    visited = []
    need_visit = [start_node]

    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
            
    return visited

※ 시간복잡도

O((V+E)*V) : V(노드의 수), E(연결의 수)

 

3. 풀이간 체크사항

 1) BFS의 가장 기본적인 문제라고 생각된다.