[자료구조] 배달 파이썬 (BFS, queue, Dijkstra, heap)

from math import inf
from collections import defaultdict, deque
from itertools import product

def solution(N, roads, K):
    answer = [inf, 0] + [inf for i in range(N-1)]
    # print(answer) # why 처음이 0이 아니라 inf로 설정했을까? -> zero 인덱스 문제를 편하게 하려고
    map = defaultdict(list) # 리스트 형태로 받겠다.
    dist_map = [[inf for _ in range(N+1)] for _ in range(N+1)]
    
    # print(dist_map)
    
    # 
    for road in roads:
        a,b,dist = road
        map[a].append(b)
        map[b].append(a) # 양쪽 노드 모두 해줘야 한다는 점이 중요
        if dist_map[a][b] > dist: # dist가 작으면 업데이트
            dist_map[a][b], dist_map[b][a] = dist,dist
    # print(map)
    # print(dist_map)            
    queue = deque([1])
    while queue:
        start = queue.popleft() # 맨처음 맨 마지막이 아니고
        end_table = map.get(start)  # start 노드와 연결된 node들의 list를 반환 
                                    # ex.{1:[2,3],...}에서 [2,3]
        for end in end_table:
            dist = answer[start] + dist_map[start][end]
            if dist < answer[end] and dist <= K:
                answer[end] = dist
                queue.append(end)
    return len(answer) - answer.count(inf)
                
        
        
        
        

 

- map을 만들때 양방향일 경우 서로 반대되는 edge에 대한 정보를 저장해 줄것.

- zero indexing을 편리하게 해결하기 위해 answer, dist_map 모두 0을 inf로 만들었다.

 

- map의 용도: start node와 연결된 다른 노드들의 정보를 저장하기 위해

- dist_map의 용도: 말 그대로 node간의 최초 dist 정보를 저장하면서 최소가 되는 dist를 업데이트 해놓는다.

- end_table은 start와 연결된 node들의 정보를 담고 있다. (여기서 하나씩 체크해가면서 탐색후 queue에 넣는다)

- queue의 용도: BFS를 사용하기 위해 가까운 node들 부터 체크해 나가는 것이다.

- answer의 용도: node 1에서 다른 node간의 거리를 저장하고 있다. (자기자신은 0으로 최초 설정 후 조건에 따라 업데이트)

 

양방향 graph 문제 여러개 풀면 암기가 될듯.

 

출처: jinomadstory.tistory.com/111

---

다익스트라로 풀면 더 빠르다고 한다. (heap: 우선순위 큐 -> 최대 최소값을 빠르게 찾는다)

 

풀어보자