[Hackerrank] [Medium] Roads and Libraries

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

Roads and Libraries | HackerRank

풀이

• 그래프가 주어졌을 때 dfs로 전체 node를 방문하기 위한 경로를 세는 문제
• 첫 번째로 도서관 짓는 비용 c_lib이 길을 설치하는 비용 c_road보다 작을 경우 각 node에 도서관을 짓는다고 보면 됨.
• dictionary를 사용해 인접행렬을 구현했고, 방향이 없기 때문에 시작노드, 끝 노드를 각각의 value에 append해줌.
• stack 방법과 visited를 사용해 하나의 노드에서 시작해 도달할 수 있는 node의 경로를 count.
  • 간단하게 extend()를 사용해 list에 덧붙였는데, extend의 timecomplexity는 O(k)라서, 만약 중복된 node를 빼고 stack에 추가할 수 있으면 더 빠르게 수행할 수 있음.
  • 경로를 셀 때는 방문 노드 수가 저장되기 때문에 1을 뺀 뒤 c_road를 곱해줘야 함.

def roadsAndLibraries(n, c_lib, c_road, cities):

    if c_lib < c_road:
        return c_lib * n

    visited = [0 for i in range(n)]
    adj_dict = {i:[] for i in range(1, n+1)}
    for city in cities:
        start, end = city[0], city[1]
        adj_dict[start].append(end)
        adj_dict[end].append(start)
    result = 0
    for start_node in adj_dict.keys():
        if visited[start_node - 1]:
            continue
        stack = [start_node]
        path_count = 0
        while stack:
            node = stack.pop()
            if visited[node-1]: continue
            visited[node-1] = 1
            stack.extend(adj_dict[node])
            path_count += 1
        result += ((path_count-1) * c_road + c_lib)
    return result