[BaekJoon] "DFS/BFS" - 백준 1697번 문제 : 숨바꼭질

[문제 설명]

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

 

- 수빈이는 현재 점 N에 있고, 동생은 점 K에 있음

- 수빈이는 걷기나 순간이동 가능

- 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 됨

- 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 됨

- 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구해야 함

 

[해결 로직]

- 아주 큰 배열을 만들어놓고, 거기에 시간을 기록하는 것임 ! (가장 빠른 시간만..)

- 현재 위치 기준으로, -1, +1, *2 일때의 값을 계속 큐에 넣어서 현재 위치에 적힌 시간 +1 을 이동하는 위치의 시간 값으로 기록함

- 대신 이동할 때, 정해진 범위내에 있고 방문하지 않은 곳이어야 함

- 만약에 시간 값이 0으로 기록되어 있다면, 그것은 방문한 곳임

- 현재 위치가 동생이 있는 지점이라면 반복문 탈출

 

[Solution 코드]

from collections import deque



if __name__ == "__main__":

    n,k = map(int, input().split())
    maxk = 100000

    q = deque()
    q.append(n)
    distary = [0 for _ in range(maxk+1)]

    while q:
        cur = q.popleft()

        if cur == k:
            break

        for nx in (cur-1, cur+1, cur*2):
            if 0<=nx<=maxk and distary[nx] == 0: ## 0인지 확인하는 것이 방문 여부 확인
                distary[nx] = distary[cur] + 1
                q.append(nx)

    print(distary[k])