[HACKERRANK] - Find the nearest clone

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

Find the nearest clone | HackerRank

주어진 val과 같은 color를 가진 node 간의 최소 거리를 출력하는 문제.

 

<My Solution>

처음에 문제를 node[val]과 같은 color를 가진 node를 찾는 문제로 잘못 이해해서 풀이하는데 쓸데없는 시간이 걸렸다.

 

BFS로 풀면 쉽게 풀리는데 아래와 같이 코드를 짜도 통과한다.

from collections import deque
def findShortest(graph_nodes, graph_from, graph_to, ids, val):
    # solve here
    visited = set()
    nodes = {i+1:[] for i in range(graph_nodes)}
    rel_nodes = []
    for a,b in zip(graph_from,graph_to):
        nodes[a].append(b)
        nodes[b].append(a)
    target = deque()
    for i in range(len(ids)):
        if ids[i] == val:
            rel_nodes.append(i+1)
    for start in rel_nodes:
        visited.clear()
        visited.add(start)
        target.append([start,0])
        while target:
            this, length = target.popleft()
            for node in nodes[this]:
                if node in visited: continue
                if ids[node-1] == val: return length+1
                visited.add(node)
                target.append([node,length+1])
    return -1

 

하지만, 

1 - 2 - 3

4 - 3

과 같이 연결되어 있을 경우 위의 코드는 2를 출력하지만 정답은 1이다.

 

따라서 코드를 아래와 같이 수정해야한다.

from collections import deque
def findShortest(graph_nodes, graph_from, graph_to, ids, val):
    # solve here
    visited = set()
    nodes = {i+1:[] for i in range(graph_nodes)}
    rel_nodes = []
    for a,b in zip(graph_from,graph_to):
        nodes[a].append(b)
        nodes[b].append(a)
    for i in range(len(ids)):
        if ids[i] == val:
            rel_nodes.append(i+1)
    res = -1
    for start in rel_nodes:
        tmp = solve(start,nodes)
        if tmp < res or res==-1: res = tmp
    return res
def solve(start,nodes):
    visited = set()
    visited.add(start)
    target = deque()
    target.append([start,0])
    while target:
        this, length = target.popleft()
        for node in nodes[this]:
            if node in visited: continue
            if ids[node-1] == val: return length+1
            visited.add(node)
            target.append([node,length+1])
    return -1