[백준] 1697. 숨바꼭질

문제 링크

문제 보기

문제

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

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

입력

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

출력

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

접근

bfs로 자신이 갈 수 있는 곳을 탐색하고, 그 깊이를 초로 잡게 되면 제일 먼저 나왔을 때가 가장 빨리 갈 수 있는 초이다.

• 그림으로 봐보자!
  

  • 예시는 수빈이가 있는 위치 = 5, 동생이 있는 위치 = 17로 잡았다.

  1. 먼저 5부터 가지를 그리면서 나간다. 숫자가 적히는 것은 큐에 넣어졌다는 것을 의미하고, 자신이 가지를 쳤을 경우에는 큐가 빠졌다는 것을 의미한다.
     ex) 5가 써졌다 -> 5가 큐에 들어간다 -> 5의 x-1, x+1, 2*x를 한다 -> 큐에서 나왔다 -> 5의 x-1, x+1, 2*x는 큐에 들어간다 <- 반복

  2. 방문한 곳은 또 방문할 필요가 없다.
     ex) 두 번째 가지에서 또 5가 나온다하면, 첫 번째 가지랑 똑같은 숫자가 반복되는 거와 마찬가지이기 때문이다.
     -> 덧붙이면, 두 번째 가지에서 5가 나와서 정답이 나올 거라면, 첫 번째 가지에서 5가 나와서 정답이 나올 것이 초가 더 빠르다.

  3. 이렇게해서 트리의 높이가 초가 된다!

수도 코드

1. 방문한 것들을 표시해줄 배열을 하나 만들어준다.
   -> 최대 길이가 100000이라고 나왔으니 100000으로 잡아줌

2. 큐에 초기 튜플 값을 넣는다. 앞의 값에는 숫자, 뒤에 값에는 지금 몇 초가 흘렀는지
   ex. 처음엔 5로 시작하면 (5, 0)

3. 큐가 없어질 때까지 반복시킨다.

4. 큐에서 숫자 하나 꺼냄
   ex. (5, 0)

5. 큐의 x-1, x+1, x*2를 큐에 넣는다. 뒤의 숫자는 +1 해서 넣음
   ex. (4, 1), (6, 1), (10, 1)

6. 동생이 있는 위치 찾으면 print(튜플의 두 번째 값)

이슈

• 100000일 때, 인덱스 에러가 났던 것이었다.
  -> visited 함수에 0~100001로 해결!
  

• 1 1 / 2 2 일 때는 당연히, 앞으로 갔다 뒤로갔다 하니까 2초가 나올 거라 생각했었다...
  -> 무조건 2초가 맞다 생각해서 이 오류 생각해내는데 한참걸림 ㅠㅠ
  -> 0초로 맞추고 해결!

코드

from collections import deque
N, K = list(map(int, input().split()))

def bfs(start):
    visited = [0 for _ in range(200001)]
    
    deq = deque()
    deq.append((start, 0))
    while len(deq)!=0:
        current, second = deq.popleft()
        if(current == K):
            print(second)
            return

        if(0<=current and current<=200000 and visited[current]==0):
                visited[current] = 1
                deq.append((current-1, second+1))
                deq.append((current+1, second+1))
                deq.append((current*2, second+1))

bfs(N)

치열한 흔적