백준 1697

문제 링크 : https://www.acmicpc.net/problem/1697

1. 아이디어

가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오

위 문구를 통해서 BFS 를 쓰기로 생각했다.

2. 해결방안

BFS 의 일반적인 문제 풀이 방식과 동일하다. Queue를 사용하였고, 현재 내 위치에서 이동할 수 있는 경우의 수는 총 3가지다

1) Current+1
2) Current-1
3) Current*2

위의 경우에 대해서 이미 방문했는지 검사한 뒤, 방문하지 않았다면 queue에 넣고 순회하는 방식이다.

3. 풀이

import sys
from collections import deque
input = sys.stdin.readline
q = deque()
n,k = map(int, input().split())
check = [False for _ in range(100001)]

def solution():
    while q:
        pos, time = q.popleft()
        if pos == k:
            print(time)
            return
        elif check[pos] == False:
            check[pos] = True
            if pos+1 < 100000 and check[pos+1] == False:
                q.append([pos+1, time+1])
            if pos-1 >= 0 and check[pos-1] == False:
                q.append([pos-1, time+1])
            if pos*2 <= 100000 and check[2*pos] == False:
                q.append([pos*2, time+1])

q.append([n,0])
solution()