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

프로그래머스 문제 풀이 - 깊이/너비 우선 탐색 (DFS/BFS)

📰 문제

문제 확인 🏃

💡 입출력 예제

3, [[1, 1, 0], [1, 1, 0], [0, 0, 1]]

>> 2

3, [[1, 1, 0], [1, 1, 1], [0, 1, 1]]

>> 1

💬 풀이

🎵 첫번째 풀이 - DFS

def solution(n, computers):
    answer = 0
    visited = [False] * n

    for idx in range(n):
        if not visited[idx]:
            answer += 1
            dfs(n, computers, idx, visited)

    return answer


def dfs(n, computers, node, visited):

    visited[node] = True

    for com in range(n):
        if not visited[com] and computers[node][com]:
            dfs(n, computers, com, visited)

🎵 두번째 풀이 - BFS

from collections import deque

def solution(n, computers):
    answer = 0
    visited = [False] * n

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

    return answer


def bfs(n, computers, node, visited):

    queue = deque()
    
    queue.append(node)
    visited[node] = True

    while queue:

        now = queue.popleft()

        for idx in range(n):
            if not visited[idx] and computers[now][idx]:
                queue.append(idx)
                visited[idx] = True

    return visited

✒️ 생각