최소신장트리2 [BOJ/PYTHON] 10423. 전기가 부족해 문제 링크: https://www.acmicpc.net/problem/10423 문제 요약 모든 도시에 전기가 공급될 수 있도록 하는 케이블 설치 최소 비용 구하기 케이블이 연결돼있는 도시에는 발전소가 하나만 존재해야 핵심 아이디어 문제를 읽으며 도시가 정점, 도시를 연결하는 케이블이 간선, 케이블 설치 비용이 비용이라는 것을 파악하고, 연결(케이블 설치)을 최소로 한다는 점에서 최소 신장 트리를 떠올리면 된다. 이미 발전소랑 연결된 도시는 연결해줄 필요가 없는데, 처음부터 발전소끼리 연결해 발전소의 최상위 부모를 만들고 시작하면 추가적으로 연결할 필요가 없다. 이후 발전소의 부모가 다를 경우에만 연결해주고, 비용을 더하면 된다. 풀이 #gold2-10423. 전기가 부족해 import sys input.. 2023. 5. 24. [BOJ/PYTHON] 6497. 전력난 백준 문제 링크: https://www.acmicpc.net/problem/6497 문제 요약 두 집 쌍에 대해 불이 켜질 수 있도록 하면서 최대로 불 꺼야 함 - 절약할 수 있는 최대 액수 구하기 핵심 아이디어 그래프 간선에 가중치가 있는 무방향 그래프가 주어지는데, 길에 불이 켜져야 하고, ‘모든’ 집을 연결하면서도 최소 비용으로 하려면 비효율적인 사이클이 발생하면 안 된다. 사이클이 없는데 최소 비용을 구하는 거라 최소 신장 트리 알고리즘을 사용하면 된다. (그 중에서 크루스칼 알고리즘을 사용함) 부모 노드가 다르면 연결해주는데, x번 집과 y번 집의 부모 노드가 같으면 이미 불이 들어온 것이기에 불을 꺼주면 된다. 불을 꺼주는 케이스에 대한 비용을 더하면 끝 풀이 #gold4-6497. 전력난 i.. 2023. 5. 24. 이전 1 다음