[해커랭크] Roads and Libraries, 각 싸이클마다 도서관이 하나씩 들어가게 하는 비용

Question

1) 도시의 개수, 2) 도서관을 짓는 비용, 3) 도로를 짓는 비용, 4) 연결 가능한 도로 (edge)가 주어지면, 모든 도시에서 도서관에 접근 가능하도록 도서관과 도로를 공사하는 최소 비용을 구하는 문제

• 연결 가능은 하더라도 굳이 연결하지 않아도 다른 도시를 통해 도서관에 갈 수 있다면 그 도로는 짓지 않아도 됨. (1->2->3)이 먼저 연결된다면 (1->3)의 도로를 짓지 않아도 된다는 뜻
• 도로 연결보다 모든 도시에 도서관을 지어버리는 게 비용이 저렴한 경우도 있음

Solution

우선 비용 측면에서 계산이 필요하다.
1) 도로 비용 >= 도서관 비용: 전체 도시에 도서관을 짓는 게 저렴
2) 도로 비용 < 도서관 비용: 가능한 범위에서 도시들을 다 잇고 각 싸이클마다 도서관을 하나씩 짓는 게 유리

아래와 같이 하나의 싸이클 내에서 도서관을 배치하는 경우에 따른 비용을 생각해보자.

도시마다 도서관을 짓는 경우: cost_lib * num_cities
모두 도로로 연결하고 도서관은 1개만 짓는 경우: cost_lib * 1 + cost_road * (num_cities-1)
도서관을 k개 짓는 경우: cost_lib * k + cost_road * (num_cities - k)

각 케이스마다 비교하는 부등식을 써 보면 결국엔 cost_lib과 cost_road를 비교해서 도로가 저렴하다면 가능한 도로로 모두 연결하고 그렇지 않다면 가능한 도서관을 많이 짓는 편이 좋다는 결론을 낼 수 있다.

PSEUDO

• 도로와 도서관 비용 비교해서 도로가 더 비싸거나 같다면 도시 개수 * 도서관 비용 return (모든 도시에 도서관)
• 연결 가능한 길 --> 그래프로 만들기(DFS를 위해)
• DFS 돌면서 실제 연결해야 하는 길의 개수 세기 (연결 가능하지만 이미 visited된 도시라면 안 가도 되기 때문)
• 한 DFS 싸이클마다 도서관을 하나씩 지어야 함
• 도로 비용 * 실제 DFS가 이동한 도로의 개수 + 도서관 비용 * 싸이클의 개수

코드 일부
DFS 돌면서 num_roads를 늘려주고, 각 싸이클마다 도서관의 수(num_cycles)를 하나씩 늘려줌. 모든 코드는 아래의 깃허브에서.

    num_roads = 0
    def dfs_helper(root):
        nonlocal graph, visited, num_roads
        visited[root] = True
        for loc in graph[root]:
            if not visited[loc]:
                num_roads += 1
                dfs_helper(loc)

    num_cycles = 0
    for city in range(1, n+1):
        if not visited[city]:
            dfs_helper(city)
            num_cycles += 1

github