Dev_Diary

https://www.acmicpc.net/problem/1197최소 스패닝 트리의 기초 문제입니다.크루스칼 알고리즘으로 풀었습니다.다만 ReculsionError 가 발생할 수 있으니 sys.setrecursionlimit() 함수를 사용해 재귀 제한을 올려준 뒤 메모리 제한을 대비해 Pypy 대신 Python 으로 채점하면 되겠습니다.import syssys.setrecursionlimit(100000)input = sys.stdin.readline## Union-Find# Uniondef Union(node1, node2, group_list): # 각 노드의 그룹 group1 = Find(node1, group_list) group2 = Find(node2, group_list) ..

https://www.acmicpc.net/problem/1647최소 스패닝 트리 문제입니다.우선 모든 마을이 연결되게 하는 최소 코스트를 구한 뒤 가장 코스트가 큰 길을 지우면 코스트 합이 가장 작은 두 개의 마을이 됩니다.import sysinput = sys.stdin.readline# 크루스칼 알고리즘을 위한 Union-Find# Uniondef Union(root_list, node_1, node_2):    # 각 노드의 루트    root_1 = Find(root_list, node_1)    root_2 = Find(root_list, node_2)    # 각 루트가 같으면    if root_1 == root_2:        return False    # 다르면 루트가 작은쪽으로 병..

https://www.acmicpc.net/problem/1197말 그대로 최소 스패닝 트리 문제입니다.크루스칼 알고리즘을 통해 쉽게 풀 수 있습니다.다만 recursion error 가 발생할 때에는 연결된 엣지의 수가 N-1 을 초과하지 않았는지 체크해주면 됩니다. import sysinput = sys.stdin.readline# 크루스칼 알고리즘을 위한 Union-Find# Uniondef Union(root_list, node_1, node_2):    # 각 노드의 루트    root_1 = Find(root_list, node_1)    root_2 = Find(root_list, node_2)    # 각 루트가 같으면    if root_1 == root_2:        return F..

https://www.acmicpc.net/problem/1922최소 스패닝 트리에 관한 문제입니다.저는 크루스칼 알고리즘을 통해 풀었습니다. 크루스칼 알고리즘은 기본적으로 그리디 알고리즘에 기반을 두고 있습니다.우선 엣지들을 코스트를 기준으로 정렬합니다.가장 낮은 코스트를 가진 엣지들을 우선적으로 선택하는데, 선택한 엣지로 인해 순환이 생기지 않는다면 선택하고 순환이 생긴다면 선택하지 않습니다.import sysinput = sys.stdin.readline# Union-Finddef Union(root_list, node_1, node_2):    # 각 루트 노드    root_1 = Find(root_list,node_1)    root_2 = Find(root_list, node_2)    # ..

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 좌표와 좌표간의 거리를 계산해 가중치로 둔 뒤 크루스칼 알고리즘을 통해 풀 수 있었습니다. import heapq import math def solution(n, data_list): # 거리 맵 dist_map = [[0 for __ in range(n)] for _ in range(n)] # 거리 맵 구성 for i in range(len(data_list)-1): for j in range(..

https://www.acmicpc.net/problem/1197 최소 스패닝 트리 알고리즘 중 하나인 크루스칼 알고리즘을 통해 쉽게 풀 수 있습니다. import sys import heapq def solution(V, E, data_list): # kruskal weight_sum, tree, union_list = kruskal(V, E, data_list) print(weight_sum) # kruskal def kruskal(V, E, data_list): # 트리, tree[i] = [i번째 노드의 자식들] tree = [[] for _ in range(V+1)] # 유니온 리스트 union_list = list(range(V+1)) # 큐 queue = [] # 데이터를 큐에 삽입 for ..