1697 숨바꼭질 _python

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

1697번: 숨바꼭질

DP 로 풀면 힘들다. 되긴 되는듯 하다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

위에도 적어뒀지만 DP로 풀면 힘들다... DP로 푼경우는 파이썬은 못찾았고 JAVA는 검색하니 나왔다.

맞춘사람을 찾아봐도 DP는 없는것 같다.

 

처음 문제를 보고 그래프가 머리속에 그려졌지만, 그래프로 접근했다간 시간초과가 날것같아서 DP를 써야할것 같았다.

그래서 DP로 풀려다가... 호되게 혼났다. 접근자체가 너무 힘들었다.

그래서 풀이를 찾아보니 그래프로 그냥 풀면 되더라.

0 100000을 입력하면 22가 나온다. 생각보다 높지않은 숫자.

그리고 시간이 빠른순으로 맞춘사람을 보면 재귀를 쓴경우가 많은것 같다.

재귀가 아닌가? 어떻게 재귀를 썼는데 64ms가 나오지..

 

3가지 경우를 deque에 저장하면서 반복하면 된다.

+1을 하는경우, -1을 하는경우, *2를 하는경우.

그리고 범위를 체크하고, 범위안에 포함된다면 방문했는지 확인하면서 횟수를 저장해나간다.

범위를 체크하는건 0<x<100000으로 체크하면 된다.

49999와 50001을 생각해보면 100000을 굳이 넘어가지 않더라도 최대값을 계산할 수 있다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

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

"""

"""

N, K = map(int,input().split())
visited = [0]*100002
queue = deque([N])

while queue:
    x = queue.popleft()
    if x==K:
        break
    for i in (x-1, x+1, x*2):
        if 0<= i <=100000 and not visited[i]:
            visited[i] = visited[x] + 1
            queue.append(i)

print(visited[K])

176ms