[伯俊13549 Python]鬼ごっこ3(Gold 5,Daextraor BFS)

アルゴリズムタイプ:マルチアウトレットまたはBFS
草は参考にならずに自分で解いたのか.△
https://www.acmicpc.net/problem/13549

SOLVE 1

다익스트라 풀이

import sys
import heapq
input = sys.stdin.readline
INF = float('inf')

N, K = map(int, input().split())

# 인접 노드들을 iterable한 값으로 리턴하기 위한 제너레이터 함수
# 코드가 간단해짐
def move(x):
    yield (x-1, 1)
    yield (x+1, 1)
    yield (2*x, 0)

# 다익스트라 알고리즘
def N_to_K(N, K):
    SSSP = [INF]*(100001)
    SSSP[N] = 0
    q = [(0, N)]
    
    while q:
        cnt_time, cnt_x = heapq.heappop(q)
        
        if cnt_time > SSSP[cnt_x]:
            continue
        
        # 0부터 100000까지의 모든 노드들은, 조건 범위 안에서
        # 자신의 -1, +1, *2의 인접 노드를 가짐
        # 그래서 제너레이터를 통해 직접 인접 노드를 구하여 순회하면 됨
        for adc_x, adc_time in move(cnt_x):
            cal_time = cnt_time + adc_time
            
            # 인접 노드로 구한 값이 조건 범위 안에 있어야 함
            if 0 <= adc_x <= 100000 and cal_time < SSSP[adc_x]:
                SSSP[adc_x] = cal_time
                heapq.heappush(q, (cal_time, adc_x))
    
    return SSSP[K]

print(N_to_K(N, K))

SOLVE 2

BFS 풀이

import sys
from collections import deque
input = sys.stdin.readline

N, K = map(int, input().split())

# BFS는 한 번 방문한 노드는 다시 방문하지 않음
# 따라서 같은 level에 대하여 인접 노드로의
# 가중치가 0인 2*x부터 방문해야 함
def move(x):
    yield (2*x, 0)
    yield (x-1, 1)
    yield (x+1, 1)

def BFS(start):
    elapsed = [-1]*(100001)
    elapsed[start] = 0
    q = deque([start])
    
    while q:
        cnt_x = q.popleft()
        
        if cnt_x == K:
            return elapsed[K]
        
        for nx, adc_time in move(cnt_x):
            cal_time = elapsed[cnt_x] + adc_time
            if 0 <= nx <= 100000 and elapsed[nx] == -1:
                elapsed[nx] = cal_time
                q.append(nx)

print(BFS(N))

SOLVE 1)プールの概要

この問題は,0または1に重み付けされた図形と考えられる.
0から10万個のノードがあり、すべてのノードは0または10万以下の範囲で-1、+1、x 2のノードと幹線が接続された図形であり、幹線の重み付け値は0または1である.
重み付けはいずれも0または正であり,あるノードからあるノードへの最短経路重み付けを求めるため,複数のアルゴリズムを用いることができる.

の既存の複数の曲線形式では、現在のノードについて、-1、+1、x 2を隣接ノードとして定義して巡回すればよい点が異なる.そのため、発電機を使います.

この場合,隣接ノードで範囲外の場合を条件文でフィルタリングする必要がある.
最後に,Kノードの最短パス重み付け値を返すと終了する.

SOLVE 2プール概要(BFSプール)
これは

BFSを少し変更した接着剤です.

BFSは,幅優先で隣接ノードを探索しながら最短経路を探索するアルゴリズムである.
しかし,この問題の目的は0と1の重みを持つ図形であるため,BFSを用いるにはいくつかの変形を考慮する必要がある.
まず,BFSが重みのないグラフィックで最初にターゲットノードを見つけたときの最短パスであることを確認する.
この問題では、幅優先検索時が最短パスであることを保証するには、グラフィック内のノードの隣接ノードを参照するときに、重み0のノードに先にアクセスする必要があります.
同じレイヤにあるノードでは、ウェイト0のノードは、同じレイヤに入る他のノードに比べて経路の長さが減少し、少なくともこれ以上増加しないように、一歩一歩行うことができる.
したがって、隣接ノードブラウズ時に重み0のノードから優先アクセスを開始するように設計されている場合、BFSの「未アクセスノード優先ブラウズ幅の論理」に従って最短パスを見つけることができる.

勉強するところ、難しいところ

ダエストロで問題を解くのは難しくないが、BFSで問題を解くのは正確ではない.他の人の解答を参考にして、BFSで解答してみましたが、この過程でダエストラとBFSの概念の間にいくつかの混同点が現れ、両者の違いをもっと詳しく学びました.基礎がしっかりしていることを実感しました.