프로그래머스: 네트워크 (python, 파이썬)

1.문제

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

코딩테스트 연습 - 네트워크

 

2. 풀이

연결이 되어있는 컴퓨터는 하나의 그룹으로 생각해서 같은 parent를 가지도록 한다.

각각의 컴퓨터가 연결되어있는 parent값을 가진 parent 리스트를 set으로 만들어 unique한 값을 가져온다,

다만 여기서는 parent를 완전히 찾아가지 않은 값이 들어있을 수 있으므로 마지막으로 parent값을 채워주는 작업을 한다.

 

3. 구현

def find(x, parent):
    if parent[x]==x:
        return x
    else:
        return find(parent[x], parent)

def uni(x, y, parent):
    x = find(x, parent)
    y = find(y, parent)
    if x==y:
        return
    parent[x]=y
    return
    
def solution(n, computers):
    answer = 0
    parent = [i for i in range(n)]
    for i in range(n):
        for j in range(n):
            if computers[i][j]==1:
                uni(i,j, parent)
    print(parent)
    
    for i in range(len(parent)):
        parent[i]=find(i,parent)
    
    answer = len(set(parent))
    return answer