[파이썬] 백준 1368 : 물대기 (골드2)

[파이썬] 백준 1368 : 물대기 (골드2)

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

---

문제

[문제]
선주는 자신이 운영하는 N개의 논에 물을 대려고 한다.
물을 대는 방법은 두 가지가 있다.
1. 하나는 직접 논에 우물을 파는 것이고 
2. 다른 하나는 이미 물을 대고 있는 다른 논으로부터 물을 끌어오는 법이다.

각각의 논에 대해 우물을 파는 비용과 논들 사이에 물을 끌어오는 비용들이 주어졌을 때, 최소의 비용으로 모든 논에 물을 대는 것이 문제이다.

[입력]
첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다.
다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다.
다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어온다.
이는 i번째 논과 j번째 논을 연결하는데 드는 비용 Pi,j(1 ≤ Pi,j ≤ 100,000, Pi,j = Pj,i, Pi,i = 0)를 의미한다.

[출력]
첫 줄에 모든 논에 물을 대는데 필요한 최소비용을 출력한다.

풀이

방향성 생각

• 각 분리집합마다 연결된 우물이 최소 한 개 있어야 한다.
• MST로 연결 후, 우물 중 가장 작은 cost의 우물을 만들면 된다.
  • -> MST를 만드는 케이스보다, 우물을 여러개 파는 경우 성립 x
• 우물 자체를 서브트리를 연결하게 해주는 하나의 노드라고 생각한다.
• 결과적으로, 우물을 제외한 노드끼리 서브트리를 구성하고 (전체가 하나의 MST로 되어있을 수 있다) 이 각 서브트리와 우물을 연결해주면 된다.

 

---

전체코드

# boj 1368 : 물대기 (골드2)

import sys
sys.setrecursionlimit(10**6) 
input = lambda : sys.stdin.readline().rstrip()

N = int(input())
matrix = [[0] + [int(input()) for _ in range(N)]]

for i in range(N):
    temp = [matrix[0][i+1]]
    temp.extend(list(map(int,input().split())))
    matrix.append(temp)

G = []
for i in range(N):
    for j in range(i+1,N+1):
        G.append((i,j,matrix[i][j]))
G.sort(key=lambda x:x[2])

P = [i for i in range(N+1)]
def find(a):
    if P[a] != a:
        P[a] = find(P[a])
    return P[a]

def union(pa,pb):
    P[max(pa,pb)] = min(pa,pb)

mst_cost = 0
for (a,b,cost) in G:

    pa,pb = find(a),find(b)
    if pa != pb:
        union(pa,pb)
        mst_cost += cost

print(mst_cost)

코멘트

• 어디서 봤던 발상인데 잘 기억은 안남...