PS73 [백준 4386] 별자리 만들기: 크루스칼 파이썬, python 1. 문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 2. 풀이 어려웠던 부분은 별이 2차원인데 1차원의 parent에 어떻게 표시하나였다. 1번 별(예: 1.0 1.0)을 0 번, 2번 별을 1번... 이런 식으로 쌍을 맞추면 된다. 또 수학적인 표현도 기억하기. parent=[i for i in range(n+2)] stars = [list(map(float, sys.stdin.readline().split())) for _ in ran.. 2021. 7. 3. [백준 1647] 도시 분할 계획: 크루스칼 (python, 파이썬) 1. 문제 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 2. 풀이 두 개로 분리한다는 것은 최소한으로 연결 한 후 가장 cost가 높은 노드를 하나 제거한다는 것이다. 3. 구현 import sys import heapq # sys.stdin = open("input.txt") N,M = map(int, sys.stdin.readline().split()) edges=[] parent=[i for i i.. 2021. 7. 3. 백준 6497번 : 전력난, 50% 에서 런타임 에러나는 경우 (python, 파이썬) 1. 문제 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 2. 풀이 와 이거 진짜.. input 에서 문제가 있다. 크루스칼만 연습하는거라면 50%까지만 봐도 될 것 같다. 50% 에서 런타임에러가 나는 경우를 해결하고 싶으면.. input에 대해 설명을 하자면, 이 부분이 문제가 된다. 우선 테스트 케이스는 다음과 같이 주어졌는데, 쉽게 생각해서 계속 받다가 0,0가 나오면 end flag이구나.. 2021. 7. 3. 백준: 네트워크 python 파이썬 1. 문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 2. 풀이 크루스칼 알고리즘의 풀이: 1. 간선을 cost 기준으로 오름차순(작->큰) 정렬 2. 연결이 안되어있으면 union + weight추가 3. 간선 v-1개가 연결되면 종료 (이번 문제에선 3번 제외) 3. 구현 import sys import heapq # sys.stdin = open("input.txt") n = int(sys.stdin.readline()) edge = int(sys.stdin.readline()) edges=[] parent=[i for i.. 2021. 7. 3. 이전 1 ··· 9 10 11 12 13 14 15 ··· 19 다음 반응형