[Baekjoon] 1697_숨바꼭질

Silver I

문제(출처: 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는 정수이다.

 

 

출력 

 

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

 

 

문제 풀이

   - my solution (Python)

import sys
from collections import deque

if __name__=='__main__':
    x,y=map(int,sys.stdin.readline().split())

    answer=[0]*100001 # 시간
    visited=[0]*100001 # 방문 여부
    visited[x]=1
    queue=deque([x])

    dx=[-1,1,2]
    flag=0
    while queue:
        temp=queue.popleft()
        for i in range(2): # -1, +1
            x=temp+dx[i]
            if x>=0 and x<=100000 and visited[x]==0: # 범위 안, 방문 x
                answer[x]=answer[temp]+1
                visited[x]=1 # 방문
                queue.append(x)
                if x==y: # 동생을 찾으면
                    flag=1
                    break
        x=temp*2
        if x >= 0 and x <= 100000 and visited[x]==0: # 범위 안, 방문 x
            answer[x] = answer[temp] + 1
            visited[x] = 1 # 방문
            queue.append(x)
            if x==y or flag==1: # 동생을 찾으면
                break
    print(answer[y])

 

❓ 왜 런타임 에러가 발생했는가?

정말 당황스럽게도 0 <= N <= 100,000 조건과 방문 여부를 확인하지 않았기 때문이다.

무슨 생각으로 그냥 탐색만 했는지 모르겠다.

 

• 수빈, 동생 위치 입력
• answer = 시간
• visited = 방문 여부
• queue가 빌 때까지 반복 -> 제일 처음 값을 pop -> 이동하려는 위치가 범위 안이며 아직 방문하지 않았다면 초 저장 및 방문 check, queue에 추가
  : 이동할 위치가 동생이 있는 곳이면 종료
  : x-1, x+1, x*2 인 경우

 

❓ java로도 문제를 풀어봤지만 똑같은 방식으로 코드를 작성하였는데 틀렸습니다가 발생했다. 

아직.... 이유를 찾지 못해서,....

---

생각🤔

 

java로는 왜 틀렸을까,,?

 

---