문제

입력 , 출력

Solution

import sys
from collections import deque

input = sys.stdin.readline


def bfs(start, end):
    dq.append((start, 0))
    visited = [0 for i in range(200002)]
    cnt = 0
    while dq:
        cur, curcnt = dq.popleft()
        if cur == end:
            cnt = curcnt
            break
        if cur + 1 <= 100000:
            if visited[cur + 1] == 0:
                visited[cur + 1] = 1
                dq.append((cur + 1, curcnt + 1))
        if cur - 1 >= 0:
            if visited[cur - 1] == 0:
                visited[cur - 1] = 1
                dq.append((cur - 1, curcnt + 1))
        if cur * 2 <= 100000:
            if visited[cur * 2] == 0:
                visited[cur * 2] = 1
                dq.append((cur * 2, curcnt + 1))
    return cnt


n, m = map(int, input().split())
dq = deque()
res = bfs(n, m)
print(res)

설명

bfs로 모든 경우의 수를 훑어보면 풀리는 문제
예외처리 핵심 부분

indexerror -> cur-1 >= 0 , cur * 2 <= 100000 확인을 먼저 해야함
visited에 바로 인덱스 접근을 해버리면 에러가 뜬다.
cur-1 >= 0 에서 같거나 클 경우를 주의 해야한다

이것만 주의하면 bfs 구현만 하면 풀린다.

후기

시험 끝나고 오랜만에 알고리즘을 하니 모르겠다...
꾸준히가 중요하다네요