인접 그래프 최소 이동거리 구하기

문제

 

이번엔 찾고자하는 타겟 val 값이 가장 가까운 vertex 까지의 거의를 반환하는 문제이다.

 

풀이

def findShortest(graph_nodes, graph_from, graph_to, ids, val):
    
    cost = -1
    graph = defaultdict(list)
    for i in range(0, len(graph_from)):
        graph[graph_from[i]].append(graph_to[i])
        graph[graph_to[i]].append(graph_from[i])
    visited = set()
    
    def bfs(start):
        visited.add(start)
        q = deque([[start, 0]])
        # ([])를 쓰면 TypeError: cannot unpack non-iterable int object
        #q = deque([start, 0])는 q=[start, 0] 으로 들어가고
        #q = deque([[start, 0]])는 q=[[start,0]] 으로 들어간다        
                
        while q:
            cur, length = q.popleft() # Idea 1
            for i in graph[cur]:
                if i not in visited:
                    if ids[i-1] == val:
                        return length + 1
                    visited.add(i)
                    q.append([i, length+1]) # Idead
        return -1
        
    for i in range(0, len(ids)):
        if ids[i] == val:
            tmp = bfs(i+1)
            if tmp > cost or cost == -1: # Idea 3
                cost = tmp
    return cost

 

끝 ! 

솔찍히 너무 오래 걸렸다. 오랜만에 해서 그런것일까, 그래도 뇌가 활성화 되는 이 기분이 너무 좋다.

 

회고 Point

위 풀이를 보면 if tmp > cost 조건문이 있는데 이해가 좀 어려웠다.

예를들어, 1-3 구간은 길이가 1이지만, 1-4 구간은 길이가 2다. 이 내용을 아래 코드에 대입해보자

# 코드
if tmp > cost or cost == -1:
    cost = tmp

# 첫번째 사이클 : 1->3 구간
if tmp(1) > cost(-1):
	cost = tmp(1)
    
# 두번째 사이클 : 1->4 구간
if tmp(2) > cost(1):
	cost = tmp(2)

우리의 목표는 최소값을 구해야하는데 이러면 최대값이 구해는게 아닌가? 라는 생각이 발목을 잡았던 것 같다. 여기서 나는 한 가지 간과한 사실이 있었다. 디버깅을 해보면, 첫번째 1 -> 3 구간 사이클에서 2를 이미 방문했기 때문에 4번 노드에서 BFS를 시작하면 2번노드까지 가지 않고 끝나버리기 때문에 최소값을 구한다고 할 수 있겠다.

 

리팩토링 Point

# Before
for i in range(0, len(graph_from)):
    graph[graph_from[i]].append(graph_to[i])
    graph[graph_to[i]].append(graph_from[i])
# After
for a,b in zip(graph_from, graph_to):
    graph[a].append(b)
    graph[b].append(a)

 

Python zip()은 두 개 이상의 iterable을 인자로 받아 각 요소를 순서대로 묶어서 튜플로 반환하는 내장 함수이다.

names = ["Alice", "Bob", "Charlie"]
ages = [25, 30, 35]
scores = [95, 80, 90]

# zip을 사용하여 세 iterable을 묶기
zipped_data = zip(names, ages, scores)

# 결과를 리스트로 변환하여 출력
result_list = list(zipped_data)
print(result_list)

 

결과는 [('Alice', 25, 95), ('Bob', 30, 80), ('Charlie', 35, 90)] 이 된다.

 

 

감사합니다.

즐거운 하루들 되세요.