⬛ [Programmers] [BFS/DFS] [Python] Level3_네트워크

문제

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

프로그래머스

풀이

# 프로그래머스 3단계 - 네트워크
from collections import deque
def bfs(graph, visited, n):
    if visited[n] == 1:
        return 0
    q = deque()
    q.append((n))
    visited[n] = 1
    while q:
        v = q.popleft()
        for i in graph[v]:
            if not visited[i]:
                visited[i] = 1
                q.append((i))
    return 1
def solution(n, computers):
    answer = 0
    graph = [[] for _ in range(n)]
    visited = [0 for _ in range(n)]
    for i in range(len(computers)):
        for j in range(len(computers[i])):
            if i == j:
                continue
            if computers[i][j] == 1:
                graph[i].append(j)
    for i in range(len(graph)):
        answer += bfs(graph, visited, i)
    return answer

print(solution(3, [[1, 1, 0], [1, 1, 1], [0, 1, 1]]))

BFS를 사용하여 풀었다. 컴퓨터 노드를 통해 그래프를 생성한 후 BFS를 통해 네트워크 개수를 세어준다. 

실수했던 것은 네트워크의 개수를 셀 때  혼자만 연결되어 있으면 예외처리를 해주지 않아서 조금 헤메었다. 

다른 부분들은 BFS 개념을 알고있다면 쉽게 해결이 가능 할 것이다.