[python] 1697번 - 숨바꼭질

문제

파이썬 풀이

이동을 1칸씩 하던 이전과 달리 한칸과 2배 이동하는 순간이동이 추가되었다.

그래서 이동 변수를 함수 안에서 설정하고 [x-1, x+1, 2 * x]로 설정하여서 해당 위치에서 탐색을 진행하도록 하였다.

그리고 이동할 때마다 저장된 값을 1씩 증가하여 시간을 기록했다.

그리고 x의 값이 k와 같으면  x에 기록된 값을 리턴하도록 하였다.

1부터 시작했기때문에 마지막 출력에서는 1을 뺀 값을 출력하도록 하였다.

그런데 처음 작성한 코드에서 시간 초과가 나왔다.

시간초과가 나온 코드

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

n, k = map(int, input().rstrip().split())
q = deque()
q.append((n,0))
visited = []
visited.append(n)

def bfs() :
    while q :
        x, day = q.popleft()
        if x == k :
            return day
        nx = [x-1, x+1, 2*x]

        for i in nx :
            if (i > 0) and (i not in visited) :
                q.append((i, day+1))
                visited.append(i)

print(bfs())

시간을 줄이기위해 무엇을 할 수 있을까 고민을 하다 not in 연산자를 그냥 인덱싱으로 바꾸기로 결정했다.

in 연산자는 시간복잡도가 O(n)이고 인덱스 접근은 시간복잡도가 O(1)이다.

바꾼 코드 (최종 코드)

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

n, k = map(int, input().rstrip().split())
l = [0]*100001
l[n] = 1
q = deque()
q.append(n)


def bfs() :
    while q :
        x= q.popleft()
        if x == k :
            return l[x]
        nx = [x-1, x+1, 2*x]

        for i in nx :
            if i < 0 or i > 100000 :
                continue
            if l[i] == 0 :
                q.append(i)
                l[i] = l[x]+1

print(bfs()-1)

visited란 빈 배열을 만들어 방문한 곳을 append한 후 나중에 방문 정보를 확인할 때 in연산자를 사용하는 것이 아닌

아예 좌표의 범위가 0~100000이므로 100001 크기의 0 리스트를 생성하여 방문한 좌표는 해당 인덱스에 방문정보를 기록하였다.

따라서 방문 정보를 확인할 때는 손쉽게 해당 인덱스로 접근할 수 있었다.

이렇게 하니 시간초과가 해결되었다.