본문 바로가기

MST5

[백준] 16562번 - 친구비 (파이썬) # 친구비 import sys import heapq input = sys.stdin.readline N, M, k = map(int, input().split()) arr = [[]for _ in range(N+1)] moneys = [0]+list(map(int, input().split())) for i in range(1, N+1): arr[0].append((moneys[i], i)) for _ in range(M): a, b = map(int, input().split()) arr[a].append((0, b)) arr[b].append((0, a)) def make_friend(): global answer q = [] heapq.heappush(q, (0, 0)) visited = [Fal.. 2022. 3. 25.
[백준] 6497번 - 전력난 (파이썬) # 전력난 import heapq import sys input = sys.stdin.readline def prim(road_info, house, start): result = 0 q = [] heapq.heappush(q, (0, start)) visited = [False] * house while q: cost, home = heapq.heappop(q) if visited[home]: continue result += cost visited[home] = True for ncost, nhome in road_info[home]: if not visited[nhome]: heapq.heappush(q, (ncost, nhome)) return result while True: house, roa.. 2022. 3. 13.
[백준] 2887번 - 행성 터널 (파이썬) # 행성 터널 import copy import heapq import sys input = sys.stdin.readline N = int(input()) planets = [] for i in range(N): x, y, z = map(int, input().split()) planets.append((x, y, z, i)) planets_x = copy.deepcopy(planets) planets_y = copy.deepcopy(planets) planets_z = copy.deepcopy(planets) planets_x.sort(key=lambda index: index[0]) planets_y.sort(key=lambda index: index[1]) planets_z.sort(key=lam.. 2022. 2. 12.
[백준] 4386번 - 별자리 만들기 (파이썬) # 별자리 만들기 import heapq import sys import math input = sys.stdin.readline N = int(input()) star = [] for _ in range(N): x, y = map(float, input().split()) star.append((x, y)) arr = [[]for _ in range(N)] for i in range(N): for j in range(N): if i == j: continue x, y = star[i][0], star[i][1] nx, ny = star[j][0], star[j][1] dist = math.sqrt(abs(x-nx)**2+abs(y-ny)**2) arr[i].append((dist, j)) result .. 2022. 2. 9.
[백준] 1647번 - 도시 분할 계획 (파이썬) MST, 프림 1. 값을 인접리스트로 받는다(양방향) 2. q에 초기값을 놓고(아무 노드) q가 빌때까지 - 현재 그래프에 연결이 안된 경우에만 (connected == False) - 연결을 해주고(connected == True) total에 비용(cost) append - 인접리스트를 for문으로 돌면서 연결이 안된 노드만 heapq에 heappush 3. max_value = total에서 가장 큰 값 4. 마을을 두곳으로 나눠야 해서 가장 비용이 큰 max_value를 sum(total)에서 빼준다. MST문제이며 크루스칼알고리즘으로도 풀 수 있다. 프림알고리즘으로 풀었다. 2022. 1. 21.

티스토리툴바