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

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

프로그래머스

---

1. 풀이

• 연결 정보를 따라 a와 b 컴퓨터의 네트워크를 합치자 (union)

컴퓨터0과 컴퓨터1의 네트워크를 합침

 

computers 연결 정보를 완전 탐색하면서 네트워크를 합친다.

이때 computers[a][b] = 1이라면 a와 b 위치가 서로 바뀐 computers[b][a] = 1이다. 이미 computers[a][b]로 컴퓨터a와 컴퓨터b의 네트워크를 합쳤기 때문에 computers[b][a] = 0으로 초기화해서 다음 번에는 굳이 네트워크를 합치지 않아도 되게 해주자.

 

 

• 네트워크 정보를 최종적으로 업데이트하자

서로 같은 네트워크에 속해도, 아직 networks에 저장된 네트워크가 최종 네트워크가 다르게 설정되어 있을 수 있다. 따라서 다시 한 번 모든 컴퓨터를 순회하면서 자신이 속한 최종 네트워크를 찾아 새로 반영해주자.

 

 

 

2. 정답 코드

• Union-Find 사용

def solution(n, computers):
    networks = [i for i in range(n)]
    
    # computers 연결 정보에 따라 union
    for i in range(n):
        for j in range(n):
            if i == j or computers[i][j] == 0:
                continue
            union(i, j, networks)
            computers[j][i] = 0  # skip this
            
    # 최상위 부모 노드로 초기화
    for i in range(n):
        root = find(i, networks)
        networks[i] = root
    return len(set(networks))

def find(node, parents):
    if node != parents[node]:
        return find(parents[node], parents)
    return node

def union(a, b, parents):
    a = find(a, parents)
    b = find(b, parents)
    
    if a < b:
        parents[b] = a
    else:
        parents[a] = b

 

• union-find 대신 dfs를 사용하는 방법도 있다.

def solution(n, computers):
    def dfs(current):
        visited[current] = True
        
        for v in range(n):
            if current != v and computers[current][v] == 1 and not visited[v]:
                dfs(v)
    
    visited = [False] * n
    answer = 0
    for v in range(n):
        if not visited[v]:
            dfs(v)
            answer += 1
        
    return answer