MST3 [백준 4386번] 별자리 만들기 문제 풀이 (with Python) 크루스칼 알고리즘과 MST(최소 신장 트리) 알고리즘을 이용했다. 별자리들의 좌표를 입력받고, 그 별자리들 중 두개씩 골라 두 별사이의 거리를 계산해서 저장한다. 두 별사이의 거리가 작은 순으로 정렬한 후, 두 별의 루트 노드가 다르면 연결해준다. import sys import math input = sys.stdin.readline def find(a): # 루트 노드 찾기 if a == parent[a]: return a parent[a] = find(parent[a]) return parent[a] def union(a, b): # 두 노드 합치기 a = find(a) b = find(b) if a .. 2023. 9. 18. [백준 6497번] 전력난 문제 풀이 (with Python) 절약할 수 있는 최대 비용의 값은 (모든 길을 연결했을 때의 비용) - (왕래할 수 있는 경로가 있는 경우의 최소 비용)을 빼면된다. 따라서, 루트 노드를 비교해 루트노드가 다르면 연결한 후, 비용을 더해 result 값에 더해주면 (왕래할 수 있는 경로가 있는 경우의 최소 비용)이 된다. z값을 모두 더한값에서 위의 값을 빼주면 된다! import sys input = sys.stdin.readline def find(x): # 루트 노드 찾는 함수 if x == parent[x]: return x else: parent[x] = find(parent[x]) return parent[x] def union(x, y): x = find(x) y = fi.. 2023. 9. 13. [백준 1922번] 네트워크 연결 문제 풀이 (with Python) 1922번: 네트워크 연결 (acmicpc.net) 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net parent = [ i for i in range(노드 수 +1) ] 로 루트 노드를 저장하는 배열을 만든다. 루트 노드가 다른 것은 연결이 안되었다는 뜻이므로, 비용이 작은 순으로 정렬하고 루트 노드가 다른 경우 연결하였다. import sys input = sys.stdin.readline def find(a): # 루트 노드 찾기 if a == parent[a]: # 루트 노드가 자신인 경우, 자기 자신 반환 return a parent[a] .. 2023. 9. 13. 이전 1 다음
