[자료구조] [python] [BFS/DFS] Shortest Reach in a Graph

Hackerrank의 Data structures 관한 문제 중에서 Hard에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. 

www.hackerrank.com/challenges/ctci-bfs-shortest-reach/problem?h_r=internal-search

BFS: Shortest Reach in a Graph | HackerRank



• 노드의 연결정보를 나타내는 n * n 매트릭스를 만든다. 두 노드가 연결되어 있다면 1, 아니면 0. 
• 특히, 매트릭스의 인덱스가 0부터 시작하므로, (node값-1) 위치에 넣어야 함을 유의한다. 이 매트릭스는 대각선들의 값이 모두 0인 대칭행렬의 특징을 가진다. 
• 추후에, 특정 시작 노드부터 n까지의 개별 노드까지의 최소 간선 거리 정보값이 있는 answer 리스트를 만든다. 초기값은 -1를 가지고 있는 것으로 만든 후, 추후에 업데이트 하는 방식으로 접근한다. 특정 노드 자신의 정보값도 포함되어 있는데, 이는 나중에 string 문자열로 전환할 때 슬라이싱하는 식으로 처리한다. 
• 너비 우선 탐색 부분(Breadth Frist Search) 이 적용된 부분은 다음과 같다. 시작 정점에서부터 가장 인접한 노드들을 먼저 방문하도록 Temp 리스트에 추가한다. Temp 리스트에 추가할 때에는 튜플 형태로 (방문 노드, 시작 노드부터의 거리값) 을 넣는다. 예) (idx, count_distance+1). 또한, 에지의 길이가 6의 배수를 따르므로, answer 리스트에 노드 위치(인덱스 값)에 거리를 넣을 때 6을 곱해줘야 함을 잊지 않는다. 
• 사소한 부분이지만, 에러가 났던 부분은 다음과 같다. 시작 노드에 따라서, answer을 슬라이싱 했을 경우 시작 노드 앞부분이 아래의 코드의 a1, 시작 노드의 뒷부분이 a2였다. 하지만, a1나 a2의 길이가 0일 경우, 문자열 공백을 입력하는데 있어서 다르게 접근해야 했다. 예를 들면, 시작 노드가 1인 경우 a1=[], a2=[6, 12, 18, -1] 일 때, ' '+'6 12 18 -1'이 되어서 앞의 띄어쓰기가 들어가기 때문이다. 이를 구분하면서 return값을 다르게 설정하였다. 

 

t = int(input())

def find_all_distance(s, matrix):
    answer = [-1]*len(matrix)
    temp = [(s,1)]
    
    while temp:
        t, count_distance = temp.pop(0)
        
        for idx, value in enumerate(matrix[t]):
            if idx == s:
                continue
            
            if value == 1 and answer[idx] == -1:
                answer[idx] = count_distance*6
                matrix[idx][t] = 'X'
                temp.append((idx,count_distance+1))
    
    a1, a2 = answer[:s], answer[s+1:]
    
    if len(a1) == 0:
        return ' '.join(list(map(str, a2)))
    elif len(a2) == 0:
        return ' '.join(list(map(str, a1)))
    else:
        a1 = ' '.join(list(map(str, a1)))
        a2 = ' '.join(list(map(str, a2)))
        return a1+' '+a2



for i in range(t):
    n, m = [int(value) for value in input().split()]
    matrix = [[0]*n for x in range(n)]
    
    for j in range(m):
        node1, node2 = [int(x) for x in input().split()]
        matrix[node1-1][node2-1], matrix[node2-1][node1-1] = 1, 1
        
        
    s = int(input())
    s -= 1
    answer = find_all_distance(s, matrix)
    
    print(answer)

 

클래스를 사용하여 문제풀이 경우는 다음과 같다. 풀이 방식은 동일하나, matrix형태로 노드의 연결정보를 나타내지 않고, n개의 리스트인 adj_lists를 만들어서, 각 노드와 연결된 인접노드 정보를 표현한 점이 다르다. 

 

class Graph(object):
    def __init__(self, n):
        self.num_nodes = n
        self.adj_lists = [[] for _ in range(n)]
    
    def connect(self, x, y):
        self.adj_lists[x].append(y)
        self.adj_lists[y].append(x)
        
    def find_all_distances(self, start):
        q = [start]
        dists = [-1]*self.num_nodes
        dists[start] = 0
        
        while q:
            cur = q.pop(0)
            for i in self.adj_lists[cur]:
                if dists[i] == -1:
                    q.append(i)
                    dists[i] = dists[cur] + 6
        for i in range(self.num_nodes):
            if i != start:
                print(dists[i], end=" ")
        print("")
        

t = int(input())
for i in range(t):
    n,m = [int(value) for value in input().split()]
    graph = Graph(n)
    for i in range(m):
        x,y = [int(x) for x in input().split()]
        graph.connect(x-1,y-1) 
    s = int(input())
    graph.find_all_distances(s-1)