백준 > 숨바꼭질

❓ 문제

백준 실버1 문제 > 숨바꼭질

❗ 해결

bfs로 풀었다.

먼저, n, k를 입력받고 이동을 체크할 리스트와 방문했는지를 확인하는 visited 리스트를 선언한다.

n, k = map(int, input().split())
check = [0] * 100_001
visited = [False] * 100_001

문제에서 1<n,k<100,000이므로, 리스트의 크기는 100,001로 초기화해준다.

그 후 bfs로 값을 찾는다.

def bfs(n,k):

    queue = deque([n])
    visited[n] = True
    while queue:

        now = queue.popleft()

        for i in [now-1, now+1, now * 2]:
            move = i

            if 0 <= move <= 100_000 and not visited[move]:
                queue.append(move)
                visited[move] = True
                check[move] = check[now] + 1

핵심은, 현재 위치가 x 일때, x + 1로 이동할지 x - 1로 이동할지, x * 2로 이동할지를 반복문을 돌면서 현재 위치를 업데이트 하고, 만약 현 위치가 1~100,000 사이이고, 방문을 하지 않은 경우에는 큐에 집어넣고, 방문 처리를 한 후, 움직인 횟수를 카운트해준다.

그 후, 목표 지점까지 얼마나 이동했는지를 출력한다.

전체코드

from collections import deque

def bfs(n,k):

    queue = deque([n])
    visited[n] = True
    while queue:

        now = queue.popleft()

        for i in [now-1, now+1, now * 2]:
            move = i

            if 0 <= move <= 100_000 and not visited[move]:
                queue.append(move)
                visited[move] = True
                check[move] = check[now] + 1

n, k = map(int, input().split())
check = [0] * 100_001
visited = [False] * 100_001

bfs(n,k)
print(check[k])