[백준 1697] 숨바꼭질

https://www.acmicpc.net/problem/1697

문제

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

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

입력

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

출력

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

입출력 예

입력	출력
5 17	4

풀이

앞에서 풀었던 문제처럼 큐와 while문을 사용했다. 수빈이가 이동할 수 있는 경우가 x=1, x+1, 2*x 세가지 경우이기 때문에 그 세가지 경우가 이미 들린 경우가 아니라면 큐에 담고 따로 생성해둔 리스트에 그 시간을 넣는 방식을 생각했다.

더 자세히 bfs의 동작을 설명하면 먼저 큐 생성 후 수빈이의 출발 지점을 큐에 넣는다. 그 다음에는 큐가 빌 때까지 while문을 수행하는데 while문에서는 크게 세가지 동작을 한다고 볼 수 있다.

1. 큐의 첫번째 원소를 pop하고 그 값을 x로 지정
2. 만약 x가 k(동생이 있는 지점)이라면 동생을 찾은 것이므로 시간을 저장해둔 result 리스트의 x번째 값을 출력하고 break
3. for문으로 x-1, x+1, 2*x의 값을 하나씩 돌면서 만약 result[i]가 0이고(처음 방문하는 지점일 때) i가 0과 100000 사이에 있으면 result[i] = result[x] + 1 (현재 지점의 시간보다 +1) 해주고 큐에 i의 값을 추가

아래 코드를 보면서 비교해보시면 이해하기 쉬울 것 같습니당

BFS를 몇번 풀어봤더니 대충 알고리즘을 어떻게 짜야하는지는 보이는 것 같다. 이 문제도 알고리즘은 금방 생각해냈는데 범위를 지정해주지 않아서 계속 런타임 에러가 났다 ㅠㅠ 다른 분들은 그런 조건까지 거는 걸 어떻게 바로 생각해내시는거지.. 아직 갈 길이 멀다

코드

from collections import deque

def bfs():
    q = deque()
    q.append(n)
    while q:
        x = q.popleft()

        if x == k:
            print(result[x])
            break

        for i in (x - 1, x + 1, x * 2):
            if result[i] == 0 and 0 <= i <= 100000:
                result[i] = result[x] + 1
                q.append(i)

    return result[k]

n, k = map(int, input().split())
result = [0] * 100001

bfs()