HackerRank [Graph Theory] Roads and Libraries /알고리즘 해커랭크

문제 주소 : www.hackerrank.com/challenges/torque-and-development/problem

 

문제 : 도서관의 수, 도시의 수, 도서관 건설비용, 도로 건설비용 값을 주고 모든 도시가 최소 하나이상의 도서관과 연결되기 위해 발생하는 최소 비용 계산

 

풀이

1. 우선 도로건설 비용보다 도서관 건설 비용이 더 저렴하면 모든곳에 도서관을 지으면 된다
2. 도시의 수만큼 2차원 리스트를 만들어 깊이우선탐색으로 이어질 수 있는 최대의 도로 길이를 구한다(도로가 더 저렴하니 최대 도로길이가 중요)
3. 도로길이*도로비용 + (도시의 수 - 도로길이)*도서관 비용 을 계산한다
4. 결과적으로 몇개의 도시가 있는지가 중요한게 아니라 최대 몇개의 도로를 이을 수 있는지가 관건이다

 

답안

import math
import os
import random
import re
import sys

# Complete the roadsAndLibraries function below.
def dfs(s,arr,visited):
    visited[s]=True
    cost=0
    for i in arr[s]:
        if(not visited[i]):
            cost+=1
            cost+=dfs(i,arr,visited)
    return cost
def roadsAndLibraries(n,m, c_lib, c_road, cities):
    if(c_lib<c_road):
        return c_lib*n
    if(m==0):
        return n*c_lib
    arr=[[0] for i in range(n+1)]
    visited=[False for i in range(n+1)]
    for i in range(1,n+1):
        arr[i][0]=i
    for i in range(m):
        arr[cities[i][0]].append(cities[i][1])
        arr[cities[i][1]].append(cities[i][0])
    vis=0
    for i in range(1,n+1):
        if(not visited[i]):
            vis+=dfs(i,arr,visited)
    cost=(((vis)*c_road)+((n-vis)*c_lib))
    return cost

if __name__ == '__main__':
    # fptr = open(os.environ['OUTPUT_PATH'], 'w')
    fptr = sys.stdout

    q = int(input())

    for q_itr in range(q):
        nmC_libC_road = input().split()

        n = int(nmC_libC_road[0])

        m = int(nmC_libC_road[1])

        c_lib = int(nmC_libC_road[2])

        c_road = int(nmC_libC_road[3])

        cities = []

        for _ in range(m):
            cities.append(list(map(int, input().rstrip().split())))

        result = roadsAndLibraries(n, m, c_lib, c_road, cities)

        fptr.write(str(result) + '\n')

    fptr.close()

 

느낀 점

처음엔 2차원 배열로 도시마다 이어진 길을 토대로 마을(혹은 섬)을 구성해서 리스트를 저장해놓은 뒤 
마을마다 도서관수*(도시수-n) + 길 수*(n)으로 최소값을 구한뒤 합치게 풀었는데
2개의 예제는 답이 틀렸고 10개정도가 타임아웃이 발생했다
그 이유로는 각 순차적으로 도시가 이어진 길 정보로 A마을 B마을를 구성하다 나중에 알고보니 A와 B가 합쳐지는경우 배열0번의 A마을와 1번의 B마을에 값이 중복으로 들어가며 오차가 발생했다
또 해당방법은 속도가 오래걸려서 이를 해결하더라도 해당 공식으론 못 푸는 문제였다

결국 다른 사람이 푼걸 보면서 디버깅하며 이해만 했던문제
깊이우선탐색을 이렇게 명시적으로(?) 써본건 처음이였다
알고리즘문제들은 깊이우선탐색, 넓이우선탐색 이 두개는 꼭 잘 다뤄야하는데..
관련문제를 더 풀어서 익혀야 겠다