[TIL]24-12-06

김슬아·2024년 12월 6일

주절주절

기본 최소 스패닝 트리 크루스칼 알고리즘의 종료조건을 바꾸면
될것같은 막연한 생각이 드는중 -> 그건 아니였고
최소 스패닝 트리 find union 공식 그대로 사용 후 최대 가중치 간선 하나만 없애면 되는 거였음..
종료조건 N-2 로 하면 안되는 이유는 스패닝 트리 완성이 안된채로 끝내버리는 거라 제거해야할 간선을 택할 수 없음.

🚀 오늘 한 일

[공부]
- 알고리즘 풀이: 도시 분할 계획 https://www.acmicpc.net/problem/1647
- 유니온 파인드 알고리즘 문제로 복습 https://www.acmicpc.net/problem/1717

🧐 새롭게 알게 된 것

핵심 포인트
- 정글에서 배웠던 개념이었는데 얼마됬다고 다 까먹어서 다시 정리 해본다.
- 최소 스패닝 트리, find-Union, 크루스칼 알고리즘
- 최소 스패닝 트리(MST) :모든 정점을 연결하는 트리,사이클이 없는 트리, 노드의 개수가 V 라면 간선의 개수는 무조건 V-1인 트리
- Union: 서로다른 두개의 집합을 하나로 병합하는 연산
- Find: 원소를 인자로 받고, 그 원소가 어떤 집합에 속해있는지(대표 노드가 무엇인지) 알려주는 함수, 보통 재귀 함수로 구현하는 듯 하다.
- 크루스칼 알고리즘:모든 간선을 가중치 오름차순으로 정렬한 뒤, Union-Find 자료구조를 사용하여 간선을 하나씩 선택하면서 사이클이 발생하지 않도록 정점을 연결한다. 이 과정을 통해 총 간선이 V-1개가 될 때까지 반복하여 최소 스패닝 트리를 만든다.
  - 현재 상태에서 가장 작은 가중치를 선택하기 때문에 그리디 알고리즘이기도 함
  - 시간 복잡도:O(ElogE) (E는 간선 수임.)
- 파이썬 자료형 Tuple: 내용물 바꿀 수 없음(불변성 보장), 리스트보다 메모리 적게 씀
- parent=list(range(n+1)) 이렇게 하면 parent의 원소가 0,1,2,...n 까지 채워지게 됨
활용 방법
- 문제를 보고 mst 문제라고 생각은 했지만, union find 방식 구현 방법이 생각이 안나서 이전에 풀어놓았던 최소스패닝트리 https://www.acmicpc.net/problem/1197 의 답을 보고 풀었다.
```
import sys
input=sys.stdin.readline
def find(x):
    if parent[x]!=x:
        parent[x]=find(parent[x])
    return parent[x]
def union(a,b):
    a,b=find(a),find(b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b
V,E=map(int,input().strip().split())
edges= sorted([tuple(map(int,input().strip().split())) for _ in range(E)], key=lambda x:x[2])
parent=list(range(V+1))
mst_weight=0
max_weight=0
edge_count=0
for a,b,weight in edges:
    if find(a)!=find(b):
        union(a,b)
        mst_weight+=weight
        max_weight = max(weight,max_weight)
        edge_count+=1
    if edge_count==V-1:
        break
print(mst_weight-max_weight)
```
- 위의 문제 답에 그대로 예시 입력을 넣어봤더니 12가 나왔다.
  나는 마을이 두개로 분할 될려면..? 에서 생각을 했는데, 간선 하나를 그냥 더 빼면 되는거 아닌가? 라고 생각했고, if edge_count==V-1: 부분을 if edge_count==V-2 로만 고치고 제출했는데 97%에서 틀리는 것이다.
- 우연찮게 예시 입력에서는 V-2 까지만 충족되어도 최소 가중치의 mst 두개가 나오는 경우였었다. 근데 우연이라기엔 거의 모든 경우 같은데..
- gpt 한테 반례를 더 꼬치꼬치 캐물어보니 이해가 갔다. N-1 부터 새로운 연결정보가 나올 수 있기 때문에 모든 마을을 연결 한 후 분리하는게 맞겠다. 이해했다.