[Python/백준] 1368. 물대기

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

크루스칼 알고리즘

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

---

현장에서 모의고사로 푼 풀이

아이디어를 도저히 못 떠올리겠어서 못 풀고 실패함.

import sys
input = sys.stdin.readline

# 입력 : 논의 수 N 1부터 시작
# 그리고 N개의 줄 동안, i번째 논에 우물을 팔 때 드는 비용
# 그 다음 N개의 줄은, 각 줄에 N개의 수가 들어오는데,
# 이는 i -> j 논 연결 비용 matrix임.


# 흠,... 일단, 뭔가 하나의 우물을 파고, 거기 기점으로 쫙 다 연결하거나,
# 아님 여러 개 우물 팔 수도 있겠음.
# 브루트 포스로는 90000^2는 무조건 넘을 거 같아서 안될거같음 아마...

# 델타 탐색인가?
# 아님 가중치인가

# 뭐지?????????????????????????????
# 흠
# MST인가?
# 가중치가 있으니 MST인 건 맞는 거 같은데, 어디에 우물을 파야할 지
# 그 기준은 어케 정하지?? 그냥 n번 다 돌려??
def fine(x):
    pass

def union(x, y):
    x_root = find(x)
    y_root = find(y)

    if x_root == y_root:


n = int(input())
cost_umul = [0]
for _ in range(n):
    cost_umul.append(int(input()))

cost_non = [list(map(int, input().split())) for _ in range(n)]


parent = list(range(n + 1))
rank = [0] * (n + 1)

min_total = 0
for i in range(n):

    total = 0
    # i번째 마을에 우물 판 거 기준으로 mst 실행해서 total 구함
    min_total = min(min_total, total)
    print(min_total)


V^2
V^2 log E

이 문제는 유니온 파인드를 이용한 크루스칼 유형의 웰 노운(잘 알려진) 아이디어로, 가상의 0번 정점을 두면 됨!!

모든 정점을 0번 정점이랑 연결하고, 그 다음에 그 그래프에 대한 MST를 구하면 답이 됨.

셀프 간선을 정의해야할 때는, 크루스칼로 풀기 굉장히 애매해지기 떄문에, 0번 정점을 넣자.

고정관념을 꺠! 내가 가지고 있는 정점만으로 MST를 돌려야 하는 게 아닐 수도 있음!

이건 경험치로 가져가면 된다. 못 떠올렸다고 좌절할 필요가 없음.

---

집와서 다시 풀어본 풀이