꼭꼭 숨어라 머리카락 보일라
(쓸 말이 없어서 아무말로 대체)

BOJ 1697 - 숨바꼭질 링크
(2022.09.07 기준 S1)
(치팅 하지마 계정차단 될라~)

문제

현재 위치가 X이면 이동 가능한 위치는 [X - 1, X + 1, X * 2] 세 곳이고 이동할 때마다 1초가 걸린다면, N에서 K로 갈 때 걸리는 최소 시간

알고리즘

현재 위치에서 1초 후에 갈 수 있는 위치로 차례대로 검사해야 하므로, BFS
DFS로 탐색하면 더 빠르게 도착할 수 있는 위치를 더 느리게 도착할 수 있으므로 BFS만 가능하다.

풀이

정말 BFS의 전형적인 문제.
N부터 시작하여 1초마다 갈 수 있는 거리를 차례대로 검사해나가면 되는데, 이미 방문한 위치는 스킵하면 된다.

이 문제의 핵심은 위치 값 저장 범위.
무조건 현재 위치 X가 K보다 작아야만 빠르게 도착할 수 있는 것이 아니다.그림과 같이 큰 값에서 감소하는 경우가 더 빠를 수도 있는데, 100,000을 넘어갔다가 다시 1씩 감소하면서 내려오는 경우도 있다는 것이다.
그러므로 위치마다 도달하는데 걸리는 시간을 저장할 배열을 만들 때, N과 K의 최대가 100,000이므로 넉넉하게 200,000으로 잡아주면 아무 문제 없어진다.

그리고 최적화를 하나 더 하자면,
현재 위치 X가 K보다 클 경우에는 더하기 1이나 곱하기 2는 아무 의미 없어진다. 그러므로 이 경우엔 빼기 1만 고려해주면 된다.

주의사항

실버 문제라 그런지 질문 게시판에 많이 올라오는 질문이 있는데
"if문에서 논리 연산 위치를 바꾸면 인덱스 에러가 뜨는데 왜 그런지 모르겠다" 라는 질문이다.
if A and B 라는 if문이 있으면, A가 참이면 B를 검사하고, A가 거짓이면 B는 검사를 하지 않는다.
if 0 <= 위치 <= 200000 and 도달시간[위치] == -1: 이라는 코드가 있다고 하면, 위치가 범위 안에 있으면 도달시간의 위치 인덱스를 검사한다. 만약 두 논리 연산 위치를 바꾸면, 위치가 범위 안에 있지 않은데 도달시간의 위치 인덱스를 검사하게 되어 인덱스 에러가 뜨는 것이다.
이 문제뿐만 아니라, 모든 문제에서 논리 연산 위치를 잘 설정하자.

코드

from collections import deque

N, K = map(int, input().split())
# 곱하기 2로 큰 위치로 갔다가 1씩 감소하면서 K에 도착하는 루트가 더 빠를 수도 있으므로
# 넉넉하게 가능한 위치를 200,000으로 잡자.
arrive = [-1] * 200001 # 0부터 200,000까지니깐 200,001개를 만든다.
arrive[N] = 0 # 수빈이가 있는 위치는 0초 걸린다.
queue = deque([N]) # 수빈이가 있는 위치부터 탐색
while arrive[K] == -1: # BFS 시작, 동생의 위치까지의 시간이 갱신될 때까지 반복
    here = queue.popleft()
    if here > K: # 만약 현재 위치가 동생의 위치보다 크다면, 곱하기 2나 더하기 1은 의미가 없다.
        if arrive[here - 1] == -1: # 그래서 빼기 1만 고려하면 된다.
            arrive[here - 1] = arrive[here] + 1
            arr
    else:
        for there in [here - 1, here + 1, here * 2]: # 갈 수 있는 위치 중에서
            if 0 <= there <= 200000 and arrive[there] == -1: # 0과 200,000 사이이고 아직 방문 전 위치라면
                arrive[there] = arrive[here] + 1 # 다음 위치까지의 시간을 갱신 후
                queue.append(there) # 덱에 다음 위치 삽입
print(arrive[K])

여담

옛날 나의 실력. 이렇게 쉬운 문제를 많이도 틀렸다.
이런걸 보다 보면, 나의 코딩 실력이 얼마나 향상됐는지 느껴지고 뿌듯하다.