네트워크 - Python, DFS, BFS, Union_find

 

 

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

프로그래머스

 

풀이 - 나의 생각

이게 왜 Lv.3일까?

 

 

 

코드

def solution(n, computers):
    def dfs(node):
        visited[node] = True
        for neighbor, connected in enumerate(computers[node]):
            if connected and not visited[neighbor]:
                dfs(neighbor)

    visited = [False] * n
    network_count = 0

    for i in range(n):
        if not visited[i]:
            dfs(i)
            network_count += 1

    return network_count

 

DFS 풀이 방식입니다.

 

방문하지 않은 컴퓨터에 접근하면서

 

방문여부를 기록해갑니다.

 

from collections import deque

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

    for i in range(n):
        if not visited[i]:
            queue = deque([i])
            network_count += 1
            
            while queue:
                now = queue.popleft()
                for neighbor, connected in enumerate(computers[now]):
                    if connected and not visited[neighbor]:
                        visited[neighbor] = True
                        queue.append(neighbor)

    return network_count

 

BFS 풀이 방식입니다.

 

DFS 방식과 동일합니다.

 

다만 한 컴퓨터에 있는 모든 연결 여부를 저장 후

 

저장된 컴퓨터를 찾아가면서 연결을 이어갑니다.

 

def solution(n, computers):
    parent = [i for i in range(n)]
    rank = [0] * n
    
    def find(x): #경로 압축
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y): #병함
        root_x = find(x)
        root_y = find(y)
        
        if root_x == root_y: #이미 같은 집합
            return
        
        if rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        elif rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        else:
            parent[root_y] = root_x
            rank[root_x] += 1
        
    for i, computer in enumerate(computers):
        for j, connected in enumerate(computer):
            if connected == 1:
                union(i, j)
    
    root_set = set()
    for i in range(n):
        root_set.add(find(i))
        
    return len(root_set)

 

Union_find 풀이 방식입니다.

 

union 후

 

find를 통해  나오는 루트 값을

 

set으로 중복 제거하여

 

나온 값을 구하는 방식입니다.

 

 

다음에 또 봐요