[프로그래머스] LEVEL3 네트워크 (유니온파인드 풀이) - 파이썬

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

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

 

[풀이 코드]

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


def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    
    if a <= b:
        parent[b] = a
    else:
        parent[a] = b
    
def solution(n, computers):
    parent = [0] * (n + 1)
    for i in range(n + 1):
        parent[i] = i

    a_list = []  # 네트워크를 연결할 컴퓨터 담기
    for i in range(n):
        for j in range(n):
            if i == j: continue
            if computers[i][j] == 1:
                union(parent, i + 1, j + 1)
                print("test", i + 1, j + 1)
    maps = {}
    for idx in range(1, len(parent)):
        v = find(parent, parent[idx])
        if not v in maps:
            maps[v] = 1

    return len(maps)

• DFS/BFS문제 파트에 있지만 유니온 파인드를 활용해서 풀었다. 원래 해결하지 못한 코드였지만 스터디를 같이 하는 형이 캐리 했던 문제..
• find함수, union함수는 거의 변함이 없지만 그냥 단순히 저 코드를 외우고 있기보단 확실하게 이해하는 게 중요했던 것 같다.
• 그리고 이 문제를 풀 때 제일 중요했던 건 마지막 for문이다. 또 항상 유니온 파인드 문제를 풀면 find함수 다음 union함수 순서였지만 이 문제를 풀 때는 순서가 바뀐 점이 중요하다.