[그래프]백준_1197_최소 스패닝 트리(Union_Find)

• 알고리즘 유형 : 최소 스패닝 트리, 크루스칼 알고리즘
• 풀이 참고 : 여러 블로그, 동기 가르침
• 문제 링크 : https://www.acmicpc.net/problem/1197

늘 언급하지만 해당 내용은 정확하지 않아 개발 공부에 도움이 되지 않습니다. 

그래서 당연히 귀한 시간 내주시어 지적해 주시면 감사 드리겠습니다. 

---

크루스칼 알고리즘

1. 상세한 정의는 다른블로그에 매우 자세히 되어 있다.

2. 역시 내가 이해한 대로 정리한다. 

  1) 그래프 내 모든 정점을 포함하며, 사이클이 되지 않고, 최소 비용(가중치의 합이 최소)이 되도록 만드는 것

  2) 문제에 주어지는 노드와 간선 정보, 가중치 값 까지 받는다. 

  3) 만약 두 연결 노드의 부모노드가 같지 않다면, union함수로 합쳐준다. 

3. 말은 이게 끝이지만 코드 흐름이 상당히 복잡하다. 

---

풀이 요약

1. 가중치를 오름차순으로 정보를 받는다.

2. 부모 노드를 우선 모두 자기 자신으로 설정한다. 

3. 연결된 노드의 부모가 같은지 찾는다. (find함수로)

4. 보낸 노드가 그 노드의 부모와 같다면 바로 해당 노드값으로 리턴

  - 다르다면 그 부모 노드의 부모값을 리턴!

  - (중요) 그 부모의 부모 노드 까지 계속 찾아서 부모노드값을 업데이트 하는 재귀가 있는데, 이부분을 사용하면 경로를 압축한다!

parent[x] = find(parent[x]) # 경로 압축

5. 그렇게 부모가 다른 노드끼리는 union으로 합친다.(union함수로)

  - 각각 해당 노드의 부모노드로 값을 비교

  - 만약 두 부모노드 중 작은 것의 현재부모를 큰 부모로 바꾼다.

---

코드(python)

import sys
input = sys.stdin.readline

# 7. union-find 연산
def union(a, b):
    a = find(a)
    b = find(b)
    if b < a:
        parent[a] = b
    else:
        parent[b] = a

def find(x):
    if x == parent[x]:
        return x
    parent[x] = find(parent[x]) # 경로 압축

    return parent[x]


# 1. v : 노드의 개수, e : 엣지의 게수
v, e = map(int, input().split())

# 2. 엣지의 정보를 받는다. 가중치는 0번째 인덱스로
tree = []
for i in range(1, e+1):
    a, b, value = map(int, input().split())
    tree.append((value, a, b))

# 3. 가중치를 기준으로 정렬
tree.sort(key=lambda x: x[0])
# tree = [(1, 1, 2), (2, 2, 3), (3, 1, 3)]

# 4. 노드별 부모 정보를 초기화 세팅 한다.(각 노드는 자기 자신을 부모로 초기화)
parent = list(range(v + 1))
# parent = [0, 1, 2, 3]

# 5. 최소 가중치 출력용 
result = 0

# 6. tree에서 노드의 부모가 누군지 확인 하고 같지않다면 union으로 합침
for c, a, b in tree:
    if find(a) != find(b):
        union(a, b)
        result += c

print(result)

---

배운 점, 배울 점

1. 3번을 풀어봐도 이해가 되지 않았던 문제이다. 

2. 내일 아침에 2번 더 풀어보자. 로직은 이제 이해가 된 것 같다. 

3. 리스트의 값을 업데이트 해주는 로직이 많이 나온다. 많이 풀어봐야 겠다.