[ BOJ 1697 ] 숨바꼭질(Python)

문제

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

수빈이는 어쩌다가 순간이동을 하게된걸까.. 🙂🙃🙂
수빈이의 위치에서 1초 후에 이동할 수 있는 3가지 경로를 체크하며 이동한다고 생각하니 쉽게 풀었던 문제다.

문제 풀이

visited 함수를 그래프로 해주었다.
방문한 숫자를 key 값으로 갖고, value는 1을 갖게끔 해주었다.

1. 1초 후에 이동할 수 있는 경로인 [n-1, n+1, 2 * n] 를 location 변수에 할당해주었다.
2. queue에 location의 요소들을 분리해서 경과 시간과 함께 넣어주었다.
   ➣ for l in location: queue.append([l,sec])
3. queue에서 pop된 이동한 경로 num과 경과 시간 sec을 체크해준다.
   num을 방문 하지 않았고, 일정 범위 안에 있을 때만 체크한다.
   3-1. 만약 num이 도착지점일 때, 이전에 다른 경로로 온 경우가 존재할 수도 있으므로 더 작은 값을 min_num 변수에 넣어준다.
   3-2. 도착지점이 아닐때, num의 방문체크를 해주고 이동할 수 있는 세가지 경로를 모두 고려해준다.
   세가지 경로 중 특정 범위내에 있고 방문하지 않은 경로를 queue에 추가해준다.
4. min_num 을 출력한다.

코드

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

MIN_NUM = 100003
n, k = map(int,input().rstrip().rsplit())
location, sec = [n-1, n+1, 2 * n] , 1
visit = {}

queue = deque()
for l in location:
    queue.append([l,sec])

if n==k:
    print(0)
    sys.exit()

while(queue):
    num, sec = queue.popleft()

    if 0 <= num and num < 100003 and visit.get(num) is None:
        if num == k:
            MIN_NUM = min(sec,MIN_NUM)
        else:
            visit[num] = 1
            if 0 <= num-1 < 100003:
                if visit.get(num-1) is None:
                    queue.append([num-1,sec+1])
            if 0 <= num+1 < 100003:
                if visit.get(num+1) is None:
                    queue.append([num+1,sec+1])
            if 0 <= num*2 < 100003:
                if visit.get(num*2) is None:
                    queue.append([num*2,sec+1])

print(MIN_NUM)