https://www.acmicpc.net/problem/1697
수빈이는 어쩌다가 순간이동을 하게된걸까.. 🙂🙃🙂
수빈이의 위치에서 1초 후에 이동할 수 있는 3가지 경로를 체크하며 이동한다고 생각하니 쉽게 풀었던 문제다.
visited 함수를 그래프로 해주었다.
방문한 숫자를 key 값으로 갖고, value는 1을 갖게끔 해주었다.
[n-1, n+1, 2 * n]
를 location 변수에 할당해주었다.for l in location: queue.append([l,sec])
num
과 경과 시간 sec
을 체크해준다.num
을 방문 하지 않았고, 일정 범위 안에 있을 때만 체크한다.num
이 도착지점일 때, 이전에 다른 경로로 온 경우가 존재할 수도 있으므로 더 작은 값을 min_num
변수에 넣어준다.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)