문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1

5 17

예제 출력 1

4

나의 코드

from sys import stdin as s
from collections import deque

# s = open("input.txt", "rt")  # 주석 처리해야 하는 부분

n, k = list(map(int, s.readline().strip().split()))

# n과 k가 유효한 범위가 100000까지이므로 
array = [0 for _ in range(100001)]

q = deque()
q.append(n)

dx = [-1, 1, 2]

# 최단 거리를 찾아야하므로 bfs로 풀이
def bfs():
   # 이 반례를 찾는데 아주 오래 걸렸답니다 ^-^
    if k <= n:
        return n - k
        
    while q:
        x = q.popleft()

        for i in range(3):
        # dx 배열에서 인덱스가 2일 때만 곱하고 나머지는 더함
            nx = x * dx[i] if i == 2 else x + dx[i]
            
            # out of range 처리
            if nx < 0 or nx > 100000:
                continue
            # 이미 방문한 경우 재방문 X
            if array[nx]:
                continue
                
           # 유효한 경우 숫자를 하나씩 늘려서 방문 처리
            array[nx] = array[x] + 1
            # bfs이므로 q에 append 하자.
            q.append(nx)
           
           # k에 대한 방문처리가 되었다면 답을 return함
            if nx == k:
                return array[nx]

print(bfs())

반례를 찾는데 오래 걸린 문제이다. 자꾸 테스트케이스는 맞는데 틀렸다고 나오길래 백준에서 질문 게시판을 뒤져보았다. 질문 게시판에 반례를 주고받는 훈훈한 광경이 아주 많더군! 근데 게시판에 있는 질문을 다 뒤져보고 반례를 모조리 대입해봐도 맞는 결과가 나오는 것이었다. 이 코드를 보기 전까쥐,,,

    if k <= n:
        return n - k

이 코드를 보기 전까지 n이 k보다 클 수도 있다는 사실은 고려를 못했었다. 맨 처음 봤을 때는 아 생각해보니 n이 k보다 크면 갈 수 있는 방법이 -1 밖에 없구나 똑똑하시군하고 넘겼다. 내 코드로는 n이 k보다 커도 잘 돌아갔기 때문이다. (그때 <이 아니라 <=인 것에 집중했어야지!!!) 계속 고민에 고민을 거듭했고 결국 n과 k가 같은 경우의 반례를 떠올리게 되었다. 휴.. 바로 통과!

내 코드에서 저 예외 처리가 없으면 n == k일 경우 답이 2가 나온다. 이걸 그렇게 늦게 알았다니.. +1 했다가 그 다음 반복 회차 때 -1을 하느라 2가 찍히는 것이다. 생각해보면 수빈이랑 동생이 같은 위치에 있는 케이스 정도는 이제 코드를 짜기 전부터 벌써 생각해봄직한 반례 아닌가? (급 반성모드,,)

여튼 오랜만에 bfs 푸니 좀 낯설기도 하다 ㅎㅎㅎㅎ 한 2달 전만 해도 bfs 재밌다고 맨날 풀었는데 다른 유형 풀고 오느라 간만에 보니 어색하구만~ 더 자주보자 브프스야 ㅋㅋㅋ 이제 타입스크립트 스터디 준비하러가쟈~~ 화이팅!