최소스패닝트리

푼 날짜 : 2024.12.26푼 문제 : [14621] / 나만 안되는 연애사용한 언어 : python알고리즘 : 최소 스패닝 트리(MST)   접근방식 :일반적인 MST 알고리즘을 사용했다.추가적으로 성별을 다르게 번갈아 가며 연결하기 위해 heap에 성별을 추가 요소로 적용했다. 문제의 조건은 다음과 같다.사심 경로는 사용자들의 사심을 만족시키기 위해 남초 대학교와 여초 대학교들을 연결하는 도로로만 이루어져 있다.사용자들이 다양한 사람과 미팅할 수 있도록 어떤 대학교에서든 모든 대학교로 이동이 가능한 경로이다.시간을 낭비하지 않고 미팅할 수 있도록 이 경로의 길이는 최단 거리가 되어야 한다.따라서 W면 M과 연결 M이라면 W와 연결하도록 구현했으며 이 과정에서 최단 거리를 계산할 수 있도록 구현했다..

푼 날짜 : 2024.12.25푼 문제 : [21924] / 도시 건설사용한 언어 : python알고리즘 : 최소 스패닝 트리(MST)   접근방식 :일반적인 MST 알고리즘을 사용했다.절약 비용을 계산하기 위해 초기 비용을 계산하고 최소 연결 비용을 계산하여 절약 금액을 도출했다.   코드 :import sysimport heapqinput = sys.stdin.readlineN, M = map(int, input().split())graph = [[] for _ in range(N+1)]visited = [0 for _ in range(N+1)]# 초기 비용을 계산하기 위함init_cost = 0for _ in range(M): A, B, C = map(int, input().split()) ..

푼 날짜 : 2024.12.24푼 문제 : [16398] / 행성 연결사용한 언어 : python알고리즘 : 최소 스패닝 트리(MST)  접근방식 :일반적인 MST 알고리즘을 사용했다.다만 평소에 리스트로 구현을 했기 때문에 행렬을 리스트로 변환하는 과정을 추가해주었다.  코드 :import sysimport heapqinput = sys.stdin.readlineN = int(input())graph = [[] for _ in range(N)]visited = [0 for _ in range(N)]# 행렬을 리스트로 변환하는 과정for i in range(N): lst = list(map(int, input().split())) for j in range(len(lst)): if..

푼 날짜 : 2024.12.23푼 문제 : [1647] / 도시 분할 계획사용한 언어 : python알고리즘 : 최소 스패닝 트리(MST)  접근방식 :문제의 요구조건을 보면  두 개의 분리된 마을로 분할마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할(각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다) => 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 위와 같은 조건을 만족하기 위해 내가 생각한 방법은 우선 전체를 연결한 비용을 계산한 후 비용이 가장 크게 드는 길을 끊어주는 것이다.  이를 위해서는 전체 비용을 계산한 후 비용이 가장 큰 길의 값을 빼주면 된다! MST 알고리즘 중 Prim 방식을 활..

푼 날짜 : 2024.12.22푼 문제 : [1922] / 네트워크 연결사용한 언어 : python알고리즘 : 최소 스패닝 트리(MST)  접근방식 :전형적인 MST 알고리즘으로 풀이했다.파이썬의 heapq를 사용하면 자동으로 최소 힙 형태로 정렬이 되기 때문에 해당 모듈을 사용하여 구현했다.   코드 :import sysimport heapqinput = sys.stdin.readlineN = int(input())M = int(input())graph = [[] for _ in range(N+1)]visited = [0 for _ in range(N+1)]for _ in range(M): a, b, c = map(int, input().split()) graph[a].append((c, b..