[Hackerrank] [Hard] BFS: Shortest Reach in a Graph

https://www.hackerrank.com/challenges/ctci-bfs-shortest-reach/problem

BFS: Shortest Reach in a Graph | HackerRank

풀이

• 그래프와 시작노드가 주어졌을 때 BFS로 다른 노드까지의 depth를 구하는 문제. 도달할 수 없으면 -1 리턴.
• BFS로 depth를 구할 때, 아래와 같은 순서대로 풀면 됨.
  • 먼저 start_node를 정의(혹은 주어짐).
  • 방문 정보를 저장할 visited 리스트 0으로 초기화. start_node에 대해서는 1로 처리
  • queue에 start_node 저장. depth는 dictionary를 사용해 depth[start_node] = 0으로 초기화.
    • 나중에 depth[next_node] = depth[current_node] + 1로 해주면 됨.

class Graph:
    def __init__(self, n):
        self.n = n
        self.adj_dict = {i:[] for i in range(n)}
        self.visited = [0 for _ in range(n)]

    def connect(self, n1, n2):
        # 방향이 없음.
        self.adj_dict[n1].append(n2)
        self.adj_dict[n2].append(n1)

    def find_all_distances(self, start_node):
        ans = []
        queue = [start_node]
        depth = {}
        self.visited[start_node] = 1
        depth[start_node+1] = 0
        # queue로 list를 사용해도 통과 했음.
        # list에서 pop(0)는 O(n)이라 오래 걸림. 
        # 이번 문제는 이렇게 list를 사용해도 통과했으나, 더 엄격한 시간복잡도를 만족하기 위해선 from collections import deque를 사용하자.
        while queue:
            node = queue.pop(0)
            for n in self.adj_dict[node]:
                # 방문하지 않은 노드일 경우
                if self.visited[n] == 0:
                    # queue에 넣어주고, 방문표시하고, depth를 늘림(여기 문제에서는 edge 길이가 6이기 때문에 6만큼 증가)
                    queue.append(n)
                    self.visited[n] = 1
                    depth[n+1] = (depth[node+1] + 6) 

        for i in range(1, self.n+1):
            # 시작 노드일 경우 결과에 포함하지 않음.
            if i == start_node+1: continue
            # key값에 있으면 도달 가능한 거리가 depth에 저장되어있음.
            if i in depth.keys():
                ans.append(depth[i])
            # key값에 없으면 도달할 수 없는 노드이기 때문에 -1를 append해줌.
            else:
                ans.append(-1)
        print(' '.join(map(str, ans)))