[프로그래머스] Level3, 네트워크 (Python)

문제

https://programmers.co.kr/learn/courses/30/lessons/43162?language=python3 

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

 

코드

import collections
def solution(n, computers):
    
    def bfs(index):
        count = -1
        check[index] = True
        queue = collections.deque()
        queue.append(index)
        while queue:
            count += 1
            cur = queue.popleft()
            for next in graph[cur]:
                if check[next] == False:
                    check[next] = True
                    queue.append(next)
        return count
    
    answer = 0
    graph = [[] for _ in range(n+1)]
    check = [False for _ in range(n+1)]
    for i in range(len(computers)):
        for j in range(len(computers[i])):
            if i == j:
                continue
            if computers[i][j] == 1:
                graph[i+1].append(j+1)
    
    for i in range(len(graph)):
        if graph[i] and check[i] == False:
            answer += bfs(i)
            print(answer)
            
    return len(computers) - answer

computers 2중 배열이 주어지면 네트워크의 수를 구하는 문제이다.

네트워크의 수는 컴퓨터 갯수(정점의 개수) - 이어진 선(간선의 개수)로 생각했다.

 

computers 배열을 인접리스트 형식으로 바꿔서 graph에 저장해줬고

bfs시작점은 graph를 for문을 돌려 다음 정점으로 연결되어 있을경우에 bfs문을 돌려줬다.

 

bfs에서 count는 0부터 시작하게 되면 while문에서 index값을 돌때부터 +1을 해주게 되서 값이 이상해져

간선의 개수를 세어주기 위해 -1부터 시작한다.