[HakerRank] Roads and Libraries

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

풀이

cost를 최소화하면서 모든 도시의 시민들이 도서관을 이용할 수 있게 하는 문제이다. 도서관이 있는 도시에 거주하거나 도서관이 있는 도시와 연결되어 있다면 해당 도시의 시민들이 도서관을 이용할 수 있다.

cost의 정의는 아래와 같다. $c_lib=cost\ of\ libarary$ $c_road=cost\ of\ road$

도서관과 도로를 짓는 방법은 두 가지로 나눌 수 있다.

1. 모든 도시에 도서관을 짓는다.
2. 모든 도시가 연결될 수 있도록 도로를 만든다.

1번 방법

c_lib가 c_road보다 작다면 1번 방법이 최선의 방법이다.

2번 방법

c_lib가 c_road보다 큰 상식적인 상황이다. 이 문제는 도시와 도시 사이의 도로를 맘대로 연결할 수 없다. 문제에서 주어진 relation만을 활용해서 도로를 지을 수 있다.

따라서 2번 방법을 수행하되 연결할 수 없는 도시 그룹들은 해당 도시 그룹만의 도서관이 필요하다.

1. 문제에서 주어진 relation을 이미 존재하는 그래프라고 간주하고 dfs를 수행한다. dfs를 수행하면서 통과하는 edge의 수를 센다.
2. 1번에서 얻은 edge의 수를 $total_path$라고 하자.
3. $total_path - num_of_city$를 통해 도시 그룹의 수를 구한다.

최종적인 cost는 아래와 같이 구할 수 있다. $total_path \times c_road+(total_path - num_of_city)\times c_city$

코드

https://github.com/naem1023/codingTest/blob/master/graph/hackerrank-roads-and-libraries.py