[BOJ / 백준] 1697 숨바꼭질 (S1 / BFS) - Python

링크

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

 

 

 

 

문제 해석

수빈이는 1초에 -1칸, 1칸, 현재의 위치의 두배 위치로 이동이 가능함
수빈이가 동생을 찾는데 걸리는 최소 시간은?


입력
첫 번째 줄 : n k
  n : 수빈의 위치
  k : 동생의 위치


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

 

 

 

 

풀이 & 코드 해석

수빈이가 n에서 조건대로 이동하여 k로 갈 수 있는 최단 거리를 구하는 문제입니다.

 

문제에서 수빈이가 이동할 수 있는 경우는 [ 앞으로 한 칸, 뒤로 한 칸, 현재 위치 2배 ]로 총 3가지 입니다.

 

 

BFS는 알고리즘 특성 상 그래프에서 특정 위치에 가장 먼저 도착하는 시간을 알 수 있습니다.

 

따라서 현재 이동 가능한 모든 경우의 수를 Queue에 삽입하고 연산하는 과정을 k에 도달할 때까지 반복하면 됩니다. 

 

https://angelplayer.tistory.com/404

[알고리즘] BFS (너비 우선 탐색)

 

 

 

 

코드

from collections import deque

def bfs(n):
    global k, ans
    q = deque()
    q.append(n)
    dis[n] = 0

    while q:
        px = q.popleft()

        nx = [px - 1, px + 1, px * 2]

        for nxt in nx:
            if nxt < 0 or nxt >= 100001:
                continue
            if dis[nxt] != -1:
                continue
            dis[nxt] = dis[px] + 1
            q.append(nxt)


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

dis = [-1] * 100001

ans = 0
bfs(n)
print(dis[k])

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java