99클럽 코테 스터디 14일차 TIL / 네트워크

네트워크

학습 키워드 : DFS, BFS, UNION&FIND
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/43162

문제 설명

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

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

문제 풀이

코드 설명

• union & find 알고리즘

# 루트 노드(여기선 값이 가장 작은 노드로 설정) 찾는 함수
def find(x):
    if parents[x] != x:
        parents[x] = find(parents[x])
    return parents[x]

# 두 원소를 같은 집합 안에 넣곡 루트 노드를 결정 짓는 함수
def union(x, y):
    x = find(x)
    y = find(y)
    if x < y:
        parents[y] = x
    else:
        parents[x] = y

def solution(n: int, computers: list):
	# parents
    global parents
    parents = [i for i in range(n)]
    
    for i in range(n-1):
        for j in range(i+1,n):
            if computers[i][j] == 1:
                union(i, j)
    
    for i in range(n):
        find(i)


    return len(set(parents))

코멘트

문제를 딱 보자마자 생각한 건 역시 union & find 알고리즘이었다. 노드와 노드를 잇는 간선들이 있을 때 연결되는 집단들을 찾을 때 가장 흔하게 쓰는 알고리즘이기 때문이다.. 한가지 주의해야 할 점은 len(set(parents))의 값을 return할 때 그 전에 모든 원소에 대해서 find(x)를 돌려줘야 한다는 점이다. 서로소 집합을 업데이트하면서 있어서 모든 원소들이 연결은 되지만 지난 노드는 루트 노드를 다른 노드로 알고 있는 경우가 있기 때문이다.