문제
풀이
백준의 숨바꼭질2 를 풀어본 사람이라면 기세등등하게 숨바꼭질3도 풀어봤을 것이다. 숨바꼭질3에서 달라진 점은 2*X 위치로 이동할 때는 시간이 걸리지 않는다는 것이다. 그래서 본인은 해당 문제를 보자마자 heapq으로 풀어봤는데 (시간 순 원소 정렬을 위해) 시간초과가 떴다. 역시 bfs의 근본은 큐 👀
먼저 숨바꼭질2와 동일하게 방문 여부 및 위치 별 최소 시간 갱신 을 위해 visited 리스트를 미리 만들어 둔다.
최대 위치가 100000이기 때문에 연산된 위치까지 고려했을 때 200000까지 공간을 만들어 둘 수 있지만 애초에 100000이 넘어버리면 해당 값을 인덱스로 갖는 visited값을 접근할 일이 없기 때문에 불필요한 메모리 낭비를 줄이기 위해 visited 리스트의 크기를 100001로 제한했다. 또한 최소 시간을 제대로 기록하기 위해 -1로 초기화해두었다. 앞서 말했 듯 2*X 위치로 이동할 때는 시간이 걸리지 않아 visited[x]가 0으로 저장될 가능성이 있기 때문이다.
이제 bfs를 돌려보자. 큐를 준비한 뒤 수빈이의 위치를 삽입한다.( = q.append(n) ) 시작 위치까지의 최소 시간은 0초 이므로 visited의 n번째는 0을 저장한다.
이후 while문을 돌며 큐에 원소가 존재한다면 원소를 pop한다.
만약 pop한 원소 x가 동생의 위치 k 라면, 가장 빠른 시간으로 수빈이가 동생을 찾았다고 간주할 수 있다. 따라서 visited[x]를 통해 최소 시간을 출력한 후 break를 통해 멈춘다.
pop한 원소 x가 k가 아니라면 아직 동생을 찾기 위한 연산 과정이 남아있다는 뜻이므로 현재 원소에서 1) 1을 뺀 경우 와 2) 1을 더한 경우 그리고 3) 2를 곱한 경우를 큐에 삽입한다.
이 때 연산된 값이 범위 내에 있는지 그리고 연산값을 인덱스로 갖는 visited 값이 -1 인지 ( = 방문했던 위치인지 파악하기 위함 ) 꼭 고려해야한다.
추가로 고려해야할 사항이 있는데, 2를 곱하는 경우는 appendleft() 를 사용하여 큐에 삽입해야 한다는 것이다. 이는 2를 곱하는 연산이 다른 연산보다 더 높은 우선수위 를 가지기 위함이다.
from collections import deque
n, k = map(int, input().split()) # n: 수빈이가 있는 위치, k: 동생이 있는 위치
q = deque()
q.append(n)
visited = [-1 for _ in range(100001)]
visited[n] = 0
while q:
x = q.popleft()
if x == k:
print(visited[x])
break
if 0 <= x - 1 < 100001 and visited[x - 1] == -1:
visited[x - 1] = visited[x] + 1
q.append(x - 1)
if 0 < x * 2 < 100001 and visited[x * 2] == -1:
visited[x * 2] = visited[x]
q.appendleft(s * 2) # 2*s 가 다른 연산보다 더 높은 우선순위를 가지기 위함
if 0 <= x + 1 < 100001 and visited[x + 1] == -1:
visited[x + 1] = visited[x] + 1
q.append(x + 1)🦾 깨달은 점
- deque는 double-ended queue의 줄임말로 양방향에서 데이터를 처리할 수 있는 구조이다. 따라서 popleft() 와 마찬가지로 appendleft() 를 통해 원소를 왼쪽에 삽입할 수 있다. appendleft()를 잘 활용해서 위 문제처럼 우선순위 처리할 때 효율적으로 사용해보자.
