나의 개발일지

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42861 🔑 프림 알고리즘 출발 위치는 상관없음 현재 섬에서 갈 수 있는 섬들을 큐에 넣고 비용이 가장 적은 길을 뽑아내 섬을 연결하는 방식 큐를 힙으로 구현했기 때문에 항상 최소 비용의 길을 뽑아내서 이동함 최소 비용의 길을 뽑아서 갔으면 또 갈 필요가 없기 때문에 방문 리스트를 통해 못 가게 막음 from collections import defaultdict from heapq import heappush, heappop def solution(n, costs): answer = 0 graph = defaultdict(list) for cost in costs: graph[cost[0]..

문제 : https://www.acmicpc.net/problem/1414 🔑 최소 비용 신장 트리, 프림 알고리즘 입력되는 문자열을 문제 형식에 맞게 숫자로 변환해서 그래프를 생성한다. ord() 함수 사용 변환한 랜선 길이의 총 합도 구해놓는다. 그리고 프림 알고리즘을 사용해 최소 비용을 구할 때마다 전체 랜선의 길이에서 빼준다. 남은 랜선의 길이가 정답인데 방문을 못한 노드가 있으면 -1을 출력한다. 더 쉬운 프림 알고리즘 문제 : https://study-yoon.tistory.com/235 import sys from heapq import heappop, heappush from collections import defaultdict input = sys.stdin.readline n = in..