[プログラマー/python]レベル2配信

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

アルゴリズム分類

BFS

問題を解く

最初は,アクセスノードを保存するアクセスリストを用いてアクセスの有無を確認し,探索を行った.しかし、もしそうなら、後で回って訪問するほうが早いかもしれません.

방문한 노드를 저장하는 변수(visit)을 사용하셨을 겁니다.
이미 방문한 노드를 다시 방문하지 않기 위해 사용하는 것인데,
중요한 것은 특정 노드를 방문했느냐 안했느냐(0 or 1)가 아닙니다.
특정 노드를 방문하는데 걸린 시간 중 최소의 값을 visit에 저장하고
특정 노드를 방문하는데 그 값보다 큰 시간이 걸리는 경우에는 탐색하지 않는 식으로 구현해보세요.

基本フレームワークは次のとおりです.
ディック・シャナリーでレストランと村を結んで時間を貯めます.
ノードごとに最小限の時間を保存し、アクセスしたディックバッテリをKの最大値500001に初期化します.
例)
{1: 500001, 2: 8, 3: 500001, 4: 500001, 5: 500001}
{1: 500001, 2: 8, 3: 500001, 4: 2, 5: 500001}
{1: 16, 2: 8, 3: 500001, 4: 2, 5: 500001}
{1: 16, 2: 8, 3: 11, 4: 2, 5: 500001}
{1: 16, 2: 8, 3: 11, 4: 2, 5: 10}
{1: 4, 2: 8, 3: 11, 4: 2, 5: 10}
{1: 4, 2: 8, 3: 11, 4: 2, 5: 4}
{1: 4, 2: 8, 3: 11, 4: 2, 5: 4}
{1: 4, 2: 6, 3: 11, 4: 2, 5: 4}
{1: 4, 2: 6, 3: 5, 4: 2, 5: 4}
その後,1を除いて2番ノードからK以下の時間であるかを確認し,結果を加えると正解となる.

ソースコード

from collections import deque

def solution(N, road, K):
    dic={i:[] for i in range(1,N+1)}

    for r in road:
        a,b,w=r
        dic[a].append((b,w))
        dic[b].append((a,w))
    
    queue=deque()
    queue.append((1,0))
    visited={i:500001 for i in range(1,N+1)}
    while queue:
        t,w=queue.popleft()
        for i in dic[t]:
            target,weight=i
            tmp=w+weight
            if visited[target]>=tmp:
                visited[target]=tmp
                queue.append((target,visited[target]))
    result=1
    for i in range(2,N+1):
        if visited[i]<=K:
            result+=1
            
    return result