[ 파이썬 ] 유니온파인드(Union Find) 관련 문제 모음

유니온파인드( Union Find )

• 한 그래프와 다른 한 그래프의 노드를 비교하여 서로 다른 그래프에 속해있다면 합쳐준다. 같은 그래프에 속해있는지 판단하는 방법은 서로의 루트노드가 같은지 비교하면 된다.

 

문제 모음

• 프로그래머스 - 네트워크 (문제로 이동)
• 프로그래머스 - 섬 연결하기 -> Union-Find 응용한 크루스칼 알고리즘 (문제로 이동)
• 백준 - 1717번 집합의 표현 (골드4) (문제로 이동)
• 백준 - 1976번 여행 가자 (골드 4) (문제로 이동) (참고)
• 백준 - 4195번 친구 네트워크 (골드 2) (문제로 이동)

2021.06.18 - [알고리즘/baekjoon] - [백준/파이썬] 친구 네트워크, 수 찾기, SHA-356

[백준/파이썬] 친구 네트워크, 수 찾기, SHA-356

---

프로그래머스 - 네트워크 (LEVEL 3)

def solution(n, computers):
    parents = [i for i in range(n)] # 초기값 각자 자기 자신을 부모로 가지고 있다

    def FindRoot(node): # 부모 노드를 찾는다
        parentNode = parents[node]
        # node의 parentnode가 자기 자신이 아닐경우 계속해서 상위노드를 탐색한다.
        if parentNode != node: 
            return FindRoot(parentNode)
        else:
            return parentNode

    def UnionSet(node1, node2): #두 노드의 부모를 병합(Union)한다
        rootNode1 = FindRoot(node1)
        rootNode2 = FindRoot(node2)
        if rootNode1 == rootNode2:
            # print(parents)
            return
        else:
            parents[rootNode1] = rootNode2
            # print(parents)
            return

    def CountRoot(parents): # 루트 노드의 갯수를 센다(덩어리 갯수 세기)
        roots = set()
        for i in range(n):
            roots.add(FindRoot(i))
        # print(roots)
        return len(set(roots))

    for node1 in range(n): # 입력값 computers에서 연결된 그래프를 찾는다
        for node2 in range(node1,n):
            if computers[node1][node2]:
                UnionSet(node1, node2)

    return CountRoot(parents)

 

+ dfs/bfs풀이 

def solution(n, computers):
	answer = 0 # 네트워크의 개수 저장
    q = [] # 탐색을 위한 큐
    visited = [0]*n # 방문한 노드 체크

    while 0 in visited: #모든값이 방문표시가 될때까지 반봇
        x = visited.index(0)
        q.append(x) # 첫 노드 인덱스 추가
        visited[x] = 1 # 첫 노드 방문 표시
        
        while q: 
            node = q.pop(0) # 큐 앞에서부터 노드 꺼내기
            visited[node] = 1
            for i in range(n): #인접 노드 방문
                if visited[i] == 0 and computers[node][i] == 1:
                    # 인접노드이고 방문한적 없는 경우
                    q.append(i) # 큐에 추가
                    visited[i] = 1 #방문했음을 표시
        answer += 1 # 한 네트워크 탐색을 마치면 개수 증가
    return answer

 

---

프로그래머스 - 섬 연결하기 (LEVEL 3)

• 크루스칼 알고리즘(Kruskal Algorithm) : 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘으로 최소 비용 신장 트리(MST)를 만들기 위한 대표적인 알고리즘
• 크루스칼 알고리즘(Kruskal Algorithm) = 유니온 파인드(Union Find) + 정렬
• 최소 가중치를 기준으로 정렬한 후 순차적으로 접근하며 두 개의 노드가 연결되어 있지 않다면 연결하고 그 간선의 가중치를 더해준다. 그리고 두 개의 노드를 병합해준다

def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x: x[2]) # 비용기준 오름차순 정렬
    parents = [i for i in range(n)]  # union-find 리스트 선언.
    
    def FindRoot(node): # 부모 노드를 찾는다
        parentNode = parents[node]
        if parentNode != node: 
            return FindRoot(parentNode)
        else:
            return parentNode

    def UnionSet(node1, node2): #두 노드의 부모를 병합(Union)한다
        rootNode1 = FindRoot(node1)
        rootNode2 = FindRoot(node2)
        if rootNode1 == rootNode2:
            return
        else:
            parents[rootNode1] = rootNode2
            return
    
    def findParent(node1, node2): # 두 노드가 연결되어 있는지 판별
        rootNode1 = FindRoot(node1)
        rootNode2 = FindRoot(node2)
        if rootNode1 == rootNode2:
            return 1
        else:
            return 0
    
    for s, d, cost in costs:
        # 두 노드가 연결되어 있지 않다면 연결시켜준다
        if findParent(s,d) != 1: 
            answer+= cost
            UnionSet(s,d)

    return answer