[백준 1697번] 숨바꼭질 (Python)

> 파이썬, 그래프 이론,그래프 탐색, 너비 우선 탐색

 

 

 

 

 

📖 문제 : 숨바꼭질 (Python)

 

 

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

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

 

 

입력

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

 

 

출력

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

 

예제 입력 1 

5 17

 

예제 출력 1 

4

 

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

 

 

 

 

내 코드

 

from collections import deque

dx = [-1, 1, 2]  # +, +, *

N, K = map(int, input().split())
dic = dict()
cnt = 0

queue = deque()
queue.append((N, cnt))
dic[N] = 1

while queue:
    x, cnt = queue.popleft()

    if x == K:
        print(cnt)
        break
    #   걷기
    for i in range(2):
        xx = x + dx[i]
        if 0 <= xx <= 100000 and dic.get(xx, 0) == 0:
            dic[xx] = 1
            queue.append((xx, cnt + 1))

        #   순간 이동
    for _ in range(1):
        xx = x * dx[2]
        if 0 <= xx <= 100000 and dic.get(xx, 0) == 0:
            dic[xx] = 1
            queue.append((xx, cnt + 1))

 

 

 

 

 

Point ! ⭐️ 

• 이 문제에서는 BFS를 사용하였습니다. 보통 탐색할 때 이미 탐색한 위치는 visited 라는 리스트를 하나 만들어 탐색했으면 1 값을 넣어 체크하는데요 ! 
  
  문제에서 수빈이의 점과 동생의 점의 범위가 각각 100,000까지 들어갈 수 있다고 100,000 사이즈를 가진 리스트를 만들기에는 너무 비효율적이라고 생각했습니다.
  
  그래서 딕셔너리를 사용하여 
  dic.get(xx, 0) 딕셔너리 안에 xx값이 없으면 0을 넣고, 0을 넣은 값은 원래 딕셔너리 값에 없었던 값이므로
  0이면 탐색하고 이미 탐색했다면 1 값을 넣어주어, 값을 찾기도 편하고, 굳이 100,000사이즈인 리스트를 만들 필요가 없도록 구현하였습니다. 

 

 

 

 

 

 

백준

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

1697번: 숨바꼭질