[HACKERRANK] - Roads and Libraries

www.hackerrank.com/challenges/torque-and-development/problem

Roads and Libraries | HackerRank

마을의 갯수 n과 도로 건설 비용 c_road, 도서관 건설 비용 c_lib, 연결 가능한 도로가 주어졌을 때,

 

모든 마을이 도서관을 이용할 수 있도록 도로 및 도서관을 건설할 때 드는 최소 비용을 구하는 문제

 

 

<My Solution>

한 집단의 최소비용은 해당 집단의 마을 수를 nn이라고 할 때, min(nn*c_lib, c_lib + (nn-1)*c_road) 이라고 할 수 있다.

 

도로 건설 비용이 더 저렴할 때, 도서관을 하나만 짓고 나머지 도로들을 연결하는 경우,

도서관 건설 비용이 더 저렴할 때, 모든 마을에 도서관을 짓는 경우 두가지 중 하나이기 때문이다.

 

먼저 도로를 연결해서 만들어질 수 있는 집단을 정리한다음 결과값을 계산.

def roadsAndLibraries(n, c_lib, c_road, cities):
    city = dict({i : set({i}) for i in range(1,n+1)})
    for bridge in cities:
        city[bridge[0]].add(bridge[1])
        city[bridge[1]].add(bridge[0])
        
    for connections in city.copy():
        if connections in city:
            connected = list(city[connections])
        while connected:
            c = connected.pop()
            if c!=connections and c in city:
                city[connections] = city[connections]|city[c]
                connected.extend(city[c])
                city.pop(c)
    res = 0
    for connections in city:
        nn = len(city[connections])
        res += min(c_lib+(nn-1)*c_road, nn*c_lib)
    return res