[python] 백준 > bfs > 숨바꼭질(1697)

[문제]

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

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

입력

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

출력

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

 

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

[풀이-1]

from collections import deque
import sys
input = sys.stdin.readline

def bfs(n):
    queue = deque([n])
    while queue:
        x = queue.popleft()
        if x == k:
            return visited[x]
        for nx in [x-1, x+1, 2*x]:
            if 0<=nx<=MAX and not visited[nx]:
                visited[nx]=visited[x]+1
                queue.append(nx)


n, k = map(int, input().split())
MAX =10**5
visited = [0]*(MAX+1)
print(bfs(n))

• visited를 활용하였다. 
• visited에 갯수를 카운트 해서 저장해준다.
• x가 k와 같을 때 visited의 x번째를 출력하면 n부터 k까지가는 최소값이 나온다.

[풀이-2]

from collections import deque
import sys
input = sys.stdin.readline


def bfs(n):
    count = 0
    queue = deque([(n, count)])
    while queue:
        val, cnt = queue.popleft()
        count = cnt
        if not visited[val]:
            visited[val]=1
            if val == k:
                return count
            count += 1
            if val-1 >= 0:
                queue.append((val-1, count))
            if val+1 <= 100000:
                queue.append((val+1, count))
            if val*2 <= 100000:
                queue.append((val*2, count))
    return count

n, k = map(int, input().split())
visited = [0]*100001
print(bfs(n))

• queue에 집어넣을 때, n뿐만 아니라 count도 같이 넣어준다.
• while문을 돌 때, queue에서 꺼낸 cnt를 count값으로 다시 초기화해준다.
• val == k 일때, count를 리턴한다.