1697 숨바꼭질

💡문제 분석 요약

• n, k가 주어졌을 때 n이 k에게 가는 최단 시간을 측정한다.
• n은 n-1 , n+1 , 2*n 이렇게 3개의 방법으로만 움직일 수 있다.

💡알고리즘 설계

• 최단경로이긴 하지만, DP처럼도 풀 수 있어보였다. n을 2*(n-1) , 2*(n+1), 2*n 이렇게 3개중에 하나로 쭉 이어나가다보면 되지 않을까 했지만 실패했다.
• 결국, 최단경로를 찾는 매커니즘은 BFS이기 때문에 BFS로 접근해야했다.

💡코드

from collections import deque

n, k = map(int, input().split())
maxSize = 100000
visited = [0] * (maxSize + 1)  # 각 위치를 방문했는지 여부 & 해당 위치까지 도달하는 데 걸린 시간
# 0이 아니니까 방문했다! 이거로 끝나는 게 아니고, 해당 숫자가 거기 인덱스까지 가는데 걸린 시간을 의미.

def bfs(start):
    queue = deque()
    queue.append(start)

    while queue:
        current = queue.popleft()
        if current == k: # 탈출 조건
            return visited[k] # value가 결국 time값. 즉, 해당 current까지 가는데 걸린 값이 value고, 시간을 의미.
        
        for next in (current+1, current-1, current * 2): # 이동할 수 있는 경우는 이 3가지뿐
            if 0 <= next <= maxSize and visited[next] == 0:
                visited[next] = visited[current] + 1
                queue.append(next)


print(bfs(n)) # visited[k]를 리턴

💡시간복잡도

• 3개의 비교를 for문에서 진행하지만 결국 O(N) 내로 끝나므로 O(N)이 될 것으로 보인다.

💡 틀린 이유

• BFS를 일차원에서 쓰는줄 모르고, DP처럼 접근했다가 틀렸다. 경험이 부족했다.
• list를 10만개 선언해도 되는지 감이 안와서 리스트 선언 안하고 어떻게 풀 수 있나 연구하다가 시간만 갔다. 

💡 틀린 부분 수정 or 다른 풀이

• 분명 DP로도 풀 수 있을 것 같아서 찾아보았다.

def solution(n, k):
    dp = defaultdict(lambda: float("inf"))
    dp[n] = 0

    for i in range(n):
        dp[i] = n - i   # n보다 작은 경우 초기화 (x-1로만 이동 가능)

    for i in range(n + 1, k + 1):
        if i % 2 == 0:
            dp[i] = min(dp[i - 1] + 1, dp[i // 2] + 1)
        else:
            dp[i] = min(dp[i - 1] + 1, dp[(i + 1) // 2] + 2) 

    return dp[k]

💡 느낀점 or 기억할정보

• ★ ★ ★ ★ ★    visited로 방문, 안방문만 나타낸게 아니고 방문시 정보까지 나타낸 것이 인상깊었다. 그동안은 안방문일때 0, 방문이면 1 즉, 0만 아니면 방문한 것으로 인식했는데 방문한 그 때의 정보도 1개 value로 넘겨줄 수 있다는 것을 꼭 기억하자 !!!!!!!!!
• 10만개의 리스트를 초기화하는 것은 너무 크다고 생각해서 안하려고 했는데 상관 없었던 것이 조금 당황스러웠다.
• 애당초 BFS를 이차원에서만 사용하는 걸로 인식했던 것이 실수였다.