[백준 1368] 물대기
1. 문제 설명
2. 문제 분석
크루스칼 알고리즘을 통해 최소 신장 트리를 구한다. 이때 i->j
간선 비용과 i->i
간선 비용을 비교해야 하는데, i->i
간선 비용을 0->i
간선으로 처리한다.
3. 나의 풀이
import sys
import heapq
n = int(sys.stdin.readline().rstrip())
pq = []
parents = [i for i in range(n+1)]
for i in range(1, n+1):
heapq.heappush(pq, [int(sys.stdin.readline().rstrip()), 0, i])
# i번에 직접 물을 대는 경우는 0번에서 i로 이어지는 간선으로 간주
for i in range(1, n+1):
line = list(map(int, sys.stdin.readline().rstrip().split()))
for j in range(1, n+1):
if i == j: continue
heapq.heappush(pq, [line[j-1], i, j])
def find(node):
if parents[node] == node: return node
else:
parents[node] = find(parents[node])
return parents[node]
def union(node1, node2):
root1, root2 = find(node1), find(node2)
if root1 == root2: return False
else:
parents[root2] = root1
return True
total = 0
while pq:
cur_cost, node1, node2 = heapq.heappop(pq)
if union(node1, node2):
total += cur_cost
# 크루스칼 알고리즘
print(total)
Author And Source
이 문제에 관하여([백준 1368] 물대기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@j_aion/백준-1368-물대기
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
크루스칼 알고리즘을 통해 최소 신장 트리를 구한다. 이때
i->j
간선 비용과i->i
간선 비용을 비교해야 하는데,i->i
간선 비용을0->i
간선으로 처리한다.
3. 나의 풀이
import sys
import heapq
n = int(sys.stdin.readline().rstrip())
pq = []
parents = [i for i in range(n+1)]
for i in range(1, n+1):
heapq.heappush(pq, [int(sys.stdin.readline().rstrip()), 0, i])
# i번에 직접 물을 대는 경우는 0번에서 i로 이어지는 간선으로 간주
for i in range(1, n+1):
line = list(map(int, sys.stdin.readline().rstrip().split()))
for j in range(1, n+1):
if i == j: continue
heapq.heappush(pq, [line[j-1], i, j])
def find(node):
if parents[node] == node: return node
else:
parents[node] = find(parents[node])
return parents[node]
def union(node1, node2):
root1, root2 = find(node1), find(node2)
if root1 == root2: return False
else:
parents[root2] = root1
return True
total = 0
while pq:
cur_cost, node1, node2 = heapq.heappop(pq)
if union(node1, node2):
total += cur_cost
# 크루스칼 알고리즘
print(total)
Author And Source
이 문제에 관하여([백준 1368] 물대기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@j_aion/백준-1368-물대기
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys
import heapq
n = int(sys.stdin.readline().rstrip())
pq = []
parents = [i for i in range(n+1)]
for i in range(1, n+1):
heapq.heappush(pq, [int(sys.stdin.readline().rstrip()), 0, i])
# i번에 직접 물을 대는 경우는 0번에서 i로 이어지는 간선으로 간주
for i in range(1, n+1):
line = list(map(int, sys.stdin.readline().rstrip().split()))
for j in range(1, n+1):
if i == j: continue
heapq.heappush(pq, [line[j-1], i, j])
def find(node):
if parents[node] == node: return node
else:
parents[node] = find(parents[node])
return parents[node]
def union(node1, node2):
root1, root2 = find(node1), find(node2)
if root1 == root2: return False
else:
parents[root2] = root1
return True
total = 0
while pq:
cur_cost, node1, node2 = heapq.heappop(pq)
if union(node1, node2):
total += cur_cost
# 크루스칼 알고리즘
print(total)
Author And Source
이 문제에 관하여([백준 1368] 물대기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@j_aion/백준-1368-물대기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)