[백준] 1697 - 숨바꼭질

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

 

알고리즘

BFS (최단거리 탐색)

 

풀이 

앞서 포스팅한 5014 - 스타트링크와 유사한 문제이다.

https://anna-in-workplace.tistory.com/60

[백준] 5014 - 스타트링크

 

이 문제는 최대 정점의 개수가 100,000개이다.

현재 지점 N에서 목표 지점 K로 이동하는 최단거리를 구하는 문제이다.

이동하는 방법은 총 3가지가 있다. 

현재 위치가 X일 때, 

1. X-1

2. X+1

3. 2*X

 

체크배열을 100,001 칸으로 만들고 앞에 방문한 횟수를 누적해서 더한다. 

 

전체 코드 

# 숨바꼭질 
# 최단거리 찾기: BFS 
from collections import deque

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

chk = [0] * (M+1)

def is_valid_coord(x):
    return 0 <= x <= M

def bfs(now):
    dq = deque()
    dq.append(now)
    chk[now] = 1 
    
    while dq:
        now = dq.popleft()
        
        if now == K:
            return chk[now] - 1 

        else:
            for nxt in (now-1, now+1, 2*now):
                if is_valid_coord(nxt) and not chk[nxt]:
                    chk[nxt] = chk[now] + 1 
                    dq.append(nxt)

print(bfs(N))