강승현입니다
article thumbnail
반응형

 

문제로이동

 

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

    #
    반응형
    profile

    강승현입니다

    @CODe_

    포스팅에 대한 피드백을 환영합니다!
    피드백 작성자를 존중하며, 함께 공유하고 성장할 수 있는 기회가 되기를 기대합니다.의견이나 조언이 있다면 언제든지 자유롭게 남겨주세요!

    profile on loading

    Loading...