문제풀이

[PY] 11724 : 연결 요소의 갯수 (Union-Find)

pwerty 2025. 3. 29. 13:26

https://www.acmicpc.net/problem/11724

 Union-Find로 하고 싶었다. 왜냐하면 이럴 때 아니면 언제 해보나 싶은거지~

Union Find ALgorittjnjrnm

    • Union-Find 알아보기
      • 왜 쓰나요? 이 아이템이 어디에 속하냐?를 논하자는 것이다.
        • 너 어디 권씨고를 타고 올라가면 권씨의 시작점이 있다.
        • 다른 사람을 붙잡아다가 권씨라면 너 어디권씨고 라고 물어 볼 수 있을 것이고 보통은 같은 최상위 부모에서 시작한다.
          • (권씨는 실제로 안동 권씨가 95% 이상이라고 알고있다)
        • 그러면 같은 조상의 권씨네요 하하 하고 제 갈길 가면 된다. 이런 알고리즘을 Union Find에서 설명한다.
      • 주요 사용되는 변수는 이와 같이 있다.
      • edgeList : 보통은 입력을 여기다가 때린다.
        • Union Find는 간선이 리스트로 정리 되어 있는 형태와 적합하다. [a, b], [a, c] 등..
        • 정렬까지에 대한 중요도는 별로..
      • parent : 부모 노드를 표기하는데 사용하는 배열이다. 일반적인 정의는 노드 갯수만큼 필요하다.
      • rank : 루트 노드 정의하는데 연산 낭비가 적도록 하는 배열이다. 트리에서 일종의 레벨을 정의한다고 생각 하면 된다.
      • totalNodes : 입력을 받던가, 간선을 받았다면 간선끼리 이러쿵 저러쿵 하던가해서 얻으면 된다.
      • CompCont : 연결된 컴포넌트의 총 갯수를 관리한다. 실제 병합이 일어날 때마다 감소한다.
        • 이거 맛깔난 아이디어인게, 어쨌든 병합은 1개 단위로 일어나니까 컴포넌트 (뭉티기)의 총 갯수가 비례해서 줄어드는 점을 상기하기 위한 변수이다. 진짜 어떤 놈이냐 만든사람, 당신은 내 서비스의 수천억 유지비용을 아낀것이다.
    • Find
      • 입력으로 node를 받는다.
      • node의 부모를 찾는데에 의의가 있다.
      • parent 변수를 활용해야한다. parent[n] 은 n의 부모 노드를 찾아 준다.
      • parent[a] 의 값이 a라면 루트 노드에 도달 한 것이니 a를 반환하고 종료한다.
    • Union
      • 입력으로 [a, b]를 받는다.
      • compA = find(a) compB = find(b) 를 하면 각 함수는 a의 최상위 부모, b의 최상위 부모를 찾아온다.
      • 만약 두 값이 동일하면 이미 같은 최상위 부모로써 Union 하는 의의가 없으니 종료
      • 하지만 위 조건문을 지나서도 작동하는 경우 CompCount -= 1 한다.
      • parent[compB] = compA :: 중요하다!
      • parent[compB] = compB
      • 둘 중 하나를 해야한다. 그럼 이걸 뭘 따져서 결정하냐 ?
        • 여기서 효율적인 방법으로 rank 변수 이용이 등장했다.
        • 한줄 : 양 쪽에서 Find로 얻은 최상위 부모 노드의 Rank에서 낮은 값쪽이 높은 쪽의 자식 노드로 병합된다.
  • Union Find를 구현하는데 있어 만들었던 코드 계획서이다. psudocode가 아니니 계획서라 했다. 보다시피 PLAN이다.

문제는 정직하게 입력을 받아서 Union Find를 수행하면 된다.

import sys

totalNodes, edgeCnt = list(map(int, sys.stdin.readline().strip().split()))
edgeList = []
parent = [0] * (totalNodes + 1)
rank = [0] * (totalNodes + 1)
compCount = totalNodes

for i in range(1, totalNodes + 1):
    parent[i] = i

for i in range(edgeCnt):
    inputA, inputB = list(map(int, sys.stdin.readline().strip().split()))
    edgeList.append([inputA, inputB])

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

def union(itemA, itemB):
    global compCount
    compA = find(itemA)
    compB = find(itemB)
    


    if(compA == compB):
        return
    
    compCount -= 1
    if(rank[compA] > rank[compB]):
        parent[compB] = compA
    elif rank[compB] > rank[compA]:
        parent[compA] = compB
    else:
        parent[compB] = compA
        rank[compA] += 1


for i in range(len(edgeList)):
    union(edgeList[i][0], edgeList[i][1])

print(compCount)