프로그래머스. 네트워크

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

프로그래머스

 

전체 코드

한승엽님 코드

def solution(n, com):
    visited = []
    que = []

    cnt = 0
    for i in range(n):
        if not i in visited:
            que.append(i)
            cnt += 1

            while que:
                x = que.pop(0)
                for i in range(n):
                    if com[x][i] == 1 and i not in visited:
                        visited.append(i)
                        que.append(i)
    return cnt

 

내가 작성한 코드 - 인접 리스트로 치환 후 BFS

import collections


def solution(n, computers):
    def bfs(graph, v, visited: set):
        queue = collections.deque([v])
        while queue:
            v = queue.popleft()
            visited.add(v)
            for w in graph[v]:
                if w not in visited:
                    queue.append(w)

    graph = collections.defaultdict(list)

    for i in range(len(computers)):
        for j in range(len(computers[i])):
            if i != j:
                if computers[i][j] == 1:
                    graph[i].append(j)

    visited = set()
    count = 0
    for i in range(n):
        if i not in visited:
            bfs(graph, i, visited)
            count += 1

    return count

 

문제에서 그래프가 인접 행렬로 주어지는 경우가 많이 있기 때문에 성능을 위해서라도 인접 리스트로 치환하지 않고 사용하는 방법을 연습해두도록 한다