[Programmers/Python] 네트워크

문제

1. 문제 난이도: 프로그래머스 Lv.3

2. 문제 요약

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

입력예시
n computers return
3 [[1, 1, 0], [1, 1, 0], [0, 0, 1]] 2
3 [[1, 1, 0], [1, 1, 1], [0, 1, 1]] 1

3. 문제 핵심: BFS, DFS

내 코드

1. 1차 시도(BFS)

from collections import deque

def BFS(n, computers, node, visited):
    queue = deque()
    queue.append(node)
    while queue:
        q = queue.popleft()
        visited[q] = True
        for i in range(n):
            if i != q and computers[q][i] == 1:
                if visited[i] == False:
                    queue.append(i)

def solution(n, computers):
    answer = 0
    visited = [False for i in range(n)]
    for com in range(n):
        if visited[com] == False:
            BFS(n, computers, com, visited)
            answer += 1
    return answer                    

2. 2차 시도(DFS)

def DFS(n, computers, node, visited):
    visited[node] = True
    for i in range(n):
        if i != node and computers[node][i] == 1:
            if visited[i] == False:
                DFS(n, computers, i, visited)


def solution(n, computers):
    answer = 0 
    visited = [False] * n
    for i in range(n):
        if visited[i] == False:
            DFS(n, computers, i, visited)
            answer += 1
    return answer