[백준] 1697 숨바꼭질

문제

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

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

입력

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

출력

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

내 풀이

from collections import deque

n, k = map(int, input().split())

q = deque()
q.append(n)

visited = [-1 for _ in range(100001)]    # 해당 숫자에 도착하는 시간을 저장
visited[n] = 0

while q:
    s = q.popleft()
    if s == k:
        print(visited[s])
        break
    
    for i in [s-1, s+1, 2*s]:
        if 0 <= i < 100001 and visited[i]==-1:
            visited[i] = visited[s]+1
            q.append(i)

시간 복잡도 → $O(N)$
BFS의 일반적인 시간 복잡도는 $O(노드\, 개수 + 간선\, 개수)$ 라고 한다.
n, k가 최대 100000이므로 노드 개수 = 100000
각 노드에서 3개의 이동 가능성 ( $x-1$ , $x+1$ , $2x$ )이 있으므로 간선의 개수는 3 $\times$ 100000
따라서 $O(400000)$ $\sim$ $O(N)$
공간 복잡도 → $O(N)$
$\because$ visited & q 사용

코멘트

최단 시간을 구하는 문제이므로 BFS(너비 우선 탐색)를 이용해서 풀어야 한다.
BFS는 보통 queue를 이용해서 탐색한다.

References

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

[백준] 12851 숨바꼭질 2

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

https://velog.io/@kupulau/%EB%B0%B1%EC%A4%80-12851-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88-2

[백준] 13549 숨바꼭질 3

https://velog.io/@kupulau/%EB%B0%B1%EC%A4%80-13549-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88-3