백준 1697 숨바꼭질

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

1697번: 숨바꼭질

📌 해결순서

문제의 범위를 확인하는것이 중요하다!!

수빈이의 위치가 0에서 출발한다면 -1, +1, *2 총 3가지의 경우가 있기 때문에 수빈이가 -1 위치로 이동하기 때문에 문제의 조건에서 벗어나게 된다. 따라서 문제의 범위에 대한 조건을 추가로 만들어 줘야한다 

MAX = 10 ** 5

 for nx in (x - 1, x + 1, x * 2):
            if 0 <= nx <= MAX and not dist[nx]:

 최근까지만 해도, 노드 방문 여부를 확인하는 배열과 문제의 답들을 저장하는 배열을 따로 만들었는데 이번 문제 같은 경우는 dist배열을 만들어서 배열의 인덱스가 좌표 + 값이 방문했을때 걸린 시간으로 만들어 주면 메모리를 더 적게 사용할 수 있다

조건에 만족하는 좌표이면 que에 계속 추가해주면서 수빈이의 동생이 있는 위치까지 계속 탐색한다

 

📌 코드

from collections import deque
import sys


def bfs():
    que = deque()
    que.append(n)

    while que:
        x = que.popleft()
        if x == k:
            print(dist[x])
            break
        for nx in (x - 1, x + 1, x * 2):
            if 0 <= nx <= MAX and not dist[nx]:
                # 다음 노드에 현재 확인하고 있는 노드값에 1을 더해준다
                # dist 노드에는 이동 횟수가 저장되는 것
                dist[nx] = dist[x] + 1
                que.append(nx)


input = sys.stdin.readline
MAX = 10 ** 5
dist = [0] * (MAX + 1)
n, k = map(int, input().split())


bfs()