티스토리 뷰

728x90

문제

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

 

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

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

programmers.co.kr

 

풀이 및 소스코드

유니온 파인드를 이용해 풀었다.

union 과정이 끝나고 나면 한 번 더 find를 통해 부모를 초기화(?) 시켜줘야한다.

해주지 않으면 TC9번을 계속 틀리게 된다 ㅠㅠ

이유 아시는 분은 댓글을 .. 달아주세요 .. 아무도 안달겠지만 ...? ...

무튼 유니온파인드에 대해 모른다면 내 티스토리에서 union을 검색해보세용

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

def find(parent, x):
    if parent[x]==x:
        return x
    parent[x] = find(parent, parent[x])
    return parent[x]
    
def solution(n, computers):
    parent = [i for i in range(n)]
    answer = 0
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if computers[i][j]==1:
                union(parent, i,j)
    for i in range(n): #이부분이 없으면 TC9번을 틀린다.
        find(parent, i)
    parent = set(parent)
    answer = len(parent)
    return answer
반응형