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

문제 이해

수빈이의 위치 N, 동생의 위치 K가 주어진다.
N에서 K로 가는 방법은 걷기(+1/-1), 순간이동(*2)이 있다.
N에서 K로 가는 가장 빠른 시간이 몇 초 후인지를 출력한다.

아이디어

BFS로 풀 수 있는 문제이다.

현재 위치에서 갈 수 있는 다음 위치들은 3가지가 있다.

• 현위치 + 1
• 현위치 - 1
• 현위치 * 2

이 다음 위치 후보들에 대해서, 특정 위치까지 가는 최단시간을 array에 저장하고 시간에 따라 갱신해준다. 이 때, 이전 초에서 이미 방문했던 위치는 재방문하지 않게 처리해 준다.

실패 코드

# https://www.acmicpc.net/problem/1697
n, k = map(int, input().split())
array = [0] * 100001

def bfs():
    queue = []
    queue.append(n)
    while queue:
        now = queue.pop(0)
        if now == k:
            return array[now]
        for next in (now+1, now-1, now*2):
            if 0 <= next < 100001 and not array[next]:
                array[next] = array[now] + 1
                queue.append(next)
print(bfs())

이렇게 풀면 런타임 에러가 뜬다.

pop(0) vs popleft()
기능은 같지만 두 함수의 시간복잡도가 다르다. pop(0)은 O(n), popleft()는 O(1)이라고 한다. pop(0)을 반복문 안에서 수행해야 하는 경우 deque 라이브러리를 사용하자.

성공 코드

# https://www.acmicpc.net/problem/1697
from collections import deque
n, k = map(int, input().split())
array = [0] * 100001

def bfs():
    queue = deque([n])
    while queue:
        now = queue.popleft()
        if now == k:
            return array[now]
        for next in (now+1, now-1, now*2):
            if 0 <= next < 100001 and not array[next]:
                array[next] = array[now] + 1
                queue.append(next)
print(bfs())

배운 것

• deque를 적극적으로 사용하자.
• pop(0)과 popleft()의 차이 기억하자.
• 문제를 보자마자 어떤 알고리즘을 사용해야 할지 먼저 알아보는 연습을 해야겠다.