코딩 테스트/크루스칼4 [백준 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. [백준 2887번 ] 행성 터널 문제 풀이 (with Python) 입출력은 동일하나, 메모리 초과가 뜬다. N이 100,000인데 128MB이므로 info의 메모리를 줄여야한다. import sys 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 < b: parent[b] = a else: parent[a] = b N = int(input()) arr = [] info = [] result = 0 parent = [i for i in range(N)] for _ in .. 2023. 9. 17. [백준 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. [백준 1674번] 도시 분할 계획 문제풀이 (with Python) 모든 마을을 연결시키는 가장 최소의 값에서 가장 큰 유지비가 드는 마을의 연결을 자르면 두 마을이 되면서 최소 유지비를 만들 수 있다. 따라서, 유지 비용이 작은 순으로 정렬하고, 루트 노드가 다를 경우 두 노드를 연결시킨다. 모든 노드를 연결한 후 가장 마지막 유지비용( 가장 큰 유지비용 )을 빼서 결과값을 도출한다. import sys 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 < b: parent[b] = a el.. 2023. 9. 13. 이전 1 다음
