문제

https://programmers.co.kr/learn/courses/30/lessons/12978

나의 코드

"""

"""

import sys
from collections import deque

# 다익스트라 알고리즘
def bfs(g, route, K, N):
    q = deque([g])
    table = [sys.maxsize] * (N+1)
    
    # 1번 마을은 배달 시작지점 이기도 하고 마을 개수 카운트에 무조건 포함 되므로 0으로 초기화 해준다.
    table[1] = 0 

    while q:
        st, dis = q.popleft()

        for en, new_dis in route[st]:

			# 1번 마을부터 시작해서 K시간 이하로 배달이 가능하고 기존의 거리보다 시간이 덜 걸린다면 업데이트 해준다.
            if dis + new_dis <= K and dis + new_dis < table[en]:
                table[en] = dis + new_dis
                q.append((en, dis + new_dis))

    return table

def solution(N, road, K):

    town_cnt = 0 # 음식 주문을 받을 수 있는 마을의 개수

    route = [ [] for _ in range(N+1) ]

	# 무방향 그래프 생성
    for a, b, dis in road:
        route[a].append((b, dis))
        route[b].append((a, dis))

	# 1번 마을에서 각 마을로 배달하므로 [1, 0] 값을 넘겨 줌.
    lst = bfs([1, 0], route, K, N)
    
    for i in lst:
        if i != sys.maxsize:
            town_cnt += 1

    return town_cnt
    

설명

문제에 주어진 그래프대로 무방향 그래프를 생성하고
1번 마을에서 배달이 시작된다는 점으로 힌트를 얻어
BFS를 구현하면 되는 문제인데 떠올리지 못했다.

참고 자료

X