[알고리즘] 네트워크

포인트

• 연결이 되어 있는지 안되어 있는지를 검사하는 방법, 방의 개수를 세는 방법으로 기억하고 있다. 
• bfs로도 풀 수 있고 dfs 로도 풀 수 있다. 그것은 각자의 자유, 둘다 완전 탐색, 그래프를 순회하는 방법이라고 생각하면 좋다.

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

python

from collections import deque


def bfs(node: int, computers: list, visited: list):
    q = deque([node])
    visited[node] = 1

    while q:
        x = q.popleft()
        for i in range(len(computers[x])):
            if visited[i] == 0 and computers[x][i] == 1:
                q.append(i)
                visited[i] = 1


def solution(n: int, computers: list) -> int:
    answer = 0
    visited = [0] * n

    for i in range(n):
        if visited[i] == 0:
            answer += 1
            bfs(i, computers, visited)

    return answer


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