[python] 백준 1697번: 숨바꼭질

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

1697번: 숨바꼭질

 

분류: BFS 

 

N 의 위치에서 K 까지 가는 최소의 이동 횟수를 구하는 문제.

 

-1 , +1 , *2 의 3가지 경우가 가능하다.

 

depth가 N일 때 전체 경우를 확인하는데에 O(N^3) 의 시간이 소요된다!

 

그래서 visited 배열을 통해 방문한 노드에 대해선 해당 노드 이후의 진행은 거부한다.

그 이유는 BFS 기 때문에,

이미 방문한 위치에 대해 다시 방문을 한다는 것은 time 이 더 크면 컸지 적은 경우는 아니기 때문이다.

최소 시간을 구하는 문제에서, 만약 5->8 로 이동하는데 시간이 2걸렸을때, 5->6->7->8 로 가는 길은 5->9로 가는 길에 비해 최소가 될 수 없다.

 

 

from sys import stdin
from _collections import deque

max_val = 100001
N, K = map(int, stdin.readline().split())

arr = [max_val] * max_val


def search(now):
    q = deque()
    next_list = []
    visited = [0] * max_val
    q.append((now,0))
    while q:
        node,t = q.popleft()
        if node == K:
            print(t)
            return
        if visited[node]:
            continue
        else:
            next_list.append(node * 2)
            next_list.append(node + 1)
            next_list.append(node - 1)
            for v in next_list:
                if 0 <= v < max_val:
                    q.append((v,t+1))
            next_list.clear()

        visited[node] = 1


search(N)

 

이후 진행가능한 *2,-1,+1 세가지 경우에 대해서는 범위가 0~100000 에 속하는 경우인지를 확인해야, visited 배열에서 index out of range 오류가 유발되지 않는다.