사용 언어: python 3.9.1

❓ Problem

백준 1697. 숨바꼭질

📕 피드백

1. 발전 방향

visited 리스트 적용을 적극적으로 고려해 봐야 한다. 특히 이런 최단 경로 비슷한 유형의 bfs의 경우 중복의 경우를 필연적으로 생각해야 하므로 더더더 적극적으로 visited 리스트 적용 고려하기.

2. 느낀점

아무래도 bfs, dfs를 한꺼번에 잡고 유형 분석을 해 나가는 게 필요해 보인다.

🚩 Solution

1. 접근법

TRY 1

우선 큐를 이용해서 BFS로 구현.

5 17의 케이스에 대해
5 -> 4, 6, 10
    4 -> 3, 5, 8
        3 -> 2 4 6
        5 -> 4 6 10
        8 -> 7 9 16
    6 -> 5, 7, 12
        5 -> 4 6 10
        7 -> 6 8 14
        12 -> 11 13 24
    10 -> 9 11 20
		...

그런데 loc-1, loc+1, loc*2 모두 조건에 상관없이 때려넣었더니 메모리 초과

TRY 2

if loc -1 >= 0: q.append(loc-1)
if loc +1 <=100000: q.append(loc+1)
if loc * 2 <= 100000: q.append(loc*2)

그런데 그래도 메모리가 초과로 뜸

TRY 3

결국 다른 분의 블로그를 참고해서 보니까 visited 리스트를 통해 연산 후 결과가 이미 방문한 숫자가 될 경우 q에 추가하지 않음.

간단하게 생각해보면 1에서 만약 0으로 간다고 할 때 1 → 2 → 1 → 0 은 최소 경로가 아니다. 즉, 1 → 2 → 1 로 되는 경우를 미리 제거해야 한다.

2. 코드

import sys; read = sys.stdin.readline
from collections import deque

N, K = tuple(map(int, read()[:-1].split(" ")))
q = deque([N]); sec = 0; find_ans = False
visited = [False]*100001

while(True):
    end = len(q); i = 0
    while(i<end):
        loc = q.popleft(); visited[loc] = True
        if loc==K: 
            find_ans = True; break
        if loc -1 >= 0 and not visited[loc-1]: q.append(loc-1)
        if loc +1 <=100000 and loc<K and not visited[loc+1]: q.append(loc+1)
        if loc * 2 <= 100000 and loc<K and not visited[loc*2]: q.append(loc*2)
        i += 1
    if find_ans: break
    sec += 1

print(sec)

3. 결과

시간 복잡도 분석

최악의 경우: O(|K-N|)