https://www.acmicpc.net/problem/1697
Problem
현재의 위치에서 -1, +1, *2 의 움직임만으로 목표 위치에 도달할 수 있다.
목표 위치에 도달하기까지의 최소 시간을 구해야한다.
위치의 범위는 0~1000000
Solution
방문했는지의 여부를 표시하는 visited 함수를 False로 모두 초기화한다.
현재 위치의 -1 값, +1 값, *2 값이 범위 내에 있고, 방문한적이 없으면 다음 턴에서 방문해준다.
-1, +1, *2 한 값 중 K와 같은 값이 나오면 종료한다.
주의할 점
처음에는 리스트에서 제일 왼쪽값을 pop 해줄 때, find = q.pop(0) 을 써주었는데 이렇게 하면 시간 복잡도가 O(n) 이 된다.
이 문제에서는 다행히 시간초과가 안나고 통과가 되었지만 deque를 이용하면 시간복잡도가 O(1)이 된다.
앞으로는 항상 deque를 선언해주어 find = q.popleft()를 이용해야겠다.
Python Code
DAilyHYUN.log