[프로그래머스 | 파이썬 python] 네트워크

깊이/너비 우선 탐색(DFS/BFS) | Find-UNION

🌏 문제

프로그래머스

 

👽 풀이 ➡️ find-union 이용

def solution(n, computers):
    def find_parent(parent, a):
        if parent[a] != a:
            parent[a] = find_parent(parent, parent[a])
        return parent[a]
    
    def union_parent(parent, a, b):
        a = find_parent(parent, a)
        b = find_parent(parent, b)
    
        if a < b:
            parent[b] = a
        else:
            parent[a] = b
    
    parent = [i for i in range(n)]

    for i in range(n):
        for j in range(i, n):
            if computers[i][j] == 1:
                union_parent(parent, i, j)
    
    for i in range(n):
        parent[i] = find_parent(parent, i)
        
    return len(set(parent))

 

👽 풀이  ➡️ BFS 이용

from collections import deque
def solution(n, computers):
    answer = 0
    visited = [False for _ in range(n)]

    def bfs(com):
        visited[com] = True
        queue = deque([])
        queue.append(com)

        while queue:
            com = queue.popleft()
            visited[com] = True
            for connect in range(n):
                if connect != com and computers[com][connect] == 1:
                    if visited[connect] == False:
                        queue.append(connect)

    for com in range(n):
        if visited[com] == False:
            bfs(com)
            answer += 1
    return answer