백준 10423 전기가 부족해 풀이 python
OnlineJudge

백준 10423 전기가 부족해 풀이 python

반응형

 

문제로이동

 

10423번: 전기가 부족해

첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째

www.acmicpc.net


목차

     


     


    문제 설명

    문제를 풀 당시에 골드2로 책정되어 있지만 사실 이보다 낮은 난이도 같습니다.

    다른 최소 스패닝트리와 차이가 하나 있다면 이미 발전소와 연결되어 있는 도시는 굳이 한번 더 연결할 필요가 없기 때문

    연결하지 않으면 됩니다.

     

    union 함수 부분에 로직을 몇가지 추가했는데, 발전소와 연결되어 있는지를 체크하기 위해서는 기존 방법(Index가 작은 곳으로 연결)대신

    발전소를 기준으로 Parent 배열을 업데이트 해야 합니다.

     

    그래서 발전소에 해당하는지를 체크하는 로직이 추가되었습니다.


    소스 코드

    Python

    import sys
    input = sys.stdin.readline
    
    N,M,K = map(int,input().split())    #도시갯수, 케이블, 발전소
    parent = [i for i in range(N+1)]
    pp = list(map(int,input().split())) #power plant 발전소
    arr = []
    
    for i in range(M):    
        a,b,d = map(int,input().split())
        arr.append([a,b,d])
    arr = sorted(arr,key=lambda x:x[2]) #가치 오름차순으로 정렬
    
    def find(x):
        if parent[x]==x:return x
        parent[x] = find(parent[x])
        return parent[x]
    def union(a,b):
        a = find(a)
        b = find(b)
        if a==b:return False
        app = a in pp
        bpp = b in pp
        if app and bpp:# 둘 다 발전소에 연결되어 있다면
            return False#굳이 연결할 필요 없음    
        if app:#a가 발전소에 연결되어 있다면
            parent[b]=a#발전소 쪽으로 연결        
        elif bpp:
            parent[a]=b        
        else:#둘 다 발전소에 연결되어 있지 않다면?
            if a<b:parent[b] = a
            else:parent[a]=b
        return True
    
    answer = 0
    for i in range(len(arr)):
        a,b,d = arr[i]    
        if union(a,b):
            answer+=d
    print(answer)

    Java8

    #
    반응형