[Hackerrank] [Medium] Find the nearest clone

https://www.hackerrank.com/challenges/find-the-nearest-clone/problem

Find the nearest clone | HackerRank

풀이

• 그래프 정보와 각 노드의 색깔 저보가 주어짐. 특정 색깔을 입력받았을 때 같은 색깔의 다른 노드에 도달할 수 있는 최단 거리를 구하는 문제
• 먼저 adj_matrix를 만들어주는데, 파이썬의 dictionary를 사용.
  • key : node, value : [인접 노드]
  • 방향이 없기 때문에 graph_from, graph_to에 있는 노드를 번갈아가며 append해줌.
• 만약 같은 색깔의 노드 개수가 2보다 작으면 -1 리턴. 검사하면서 색깔 정보를 기준으로 start_node를 구함.
• start_node에 대해 BFS수행하며 최단거리를 계산해줌.

def findShortest(graph_nodes, graph_from, graph_to, colors, target_color):
    from collections import defaultdict
    from collections import deque
    adj_dict = defaultdict(list)
    color_dict = {}
    # adj_matrix 만들어줌.
    for idx in range(len(graph_from)):
        start_ = graph_from[idx]
        end_ = graph_to[idx]
        adj_dict[start_].append(end_)
        adj_dict[end_].append(start_)

    for idx, val in enumerate(colors):
        color_dict[idx+1] = val

    cnt = 0
    start_node = []
    for key, val in color_dict.items():
        if target_color == val:
            cnt += 1
            start_node.append(key)
    # 같은 색깔 노드 개수가 2보다 작으면 -1 리턴
    if cnt < 2:
        return -1

    answer = []
    depth = {}

    # 모든 시작 노드에 대해 BFS수행 -> 같은 색깔 node와의 거리 구함.
    for start in start_node:
        queue = deque([start])
        depth[start] = 0
        visited = [0] * (len(colors)+1)
        visited[start] = 1
        while queue:
            node = queue.popleft()
            for adj_node in adj_dict[node]:
                if visited[adj_node] : continue
                if colors[adj_node-1] == target_color:
                    answer.append(depth[node] + 1)

                if visited[adj_node] != 1:
                    visited[adj_node] = 1
                    queue.append(adj_node)
                    depth[adj_node] = depth[node] + 1

    # answer 중 최솟값을 return, 비어있으면 -1
    return min(answer) if answer != [] else -1