BFS 백준 - 1697 [Python]

• 목적은 임의의 정점에서 시작해서, 모든 정점을 한 번씩 방문하는 것이다.
• BFS는 모든 가중치가 1일때, 최단 거리를 구하는 알고리즘이다. - 최소비용 문제이어야 한다.
• 가중치가 1이 아닐때에는 다익스트라 알고리즘을 사용해야 한다.
• 정점과 간서의 개수가 적어야 한다.

Problem)

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

Solution)

입력의 제한은 10만, 갈 수 있는 것은 20만이 최대가 된다.

• check[i] = i를 방문했는지
• dist[i] = i를 몇 번만에 방문했는지

Answer)

from collections import deque

MAX = 200000
check = [False]*(MAX+1)
dist = [-1]*(MAX+1)

n,m = map(int, input().split())
check[n] = True
dist[n]=0

q = deque()
q.append(n)
while q:
    now = q.popleft()
    for nxt in [now-1, now+1, now*2]:
        if 0<=nxt<=MAX and check[nxt] == False:
            check[nxt] = True
            dist[nxt] = dist[now]+1
            q.append(nxt)
            
print(dist[m])