파이썬 1697번 숨바꼭질 파이썬 풀이

파이썬  1697번 숨바꼭질 파이썬 풀이

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

---

풀이과정

첫 코드(시간초과)

#숨바꼭질

from collections import deque


N,K = map(int,input().split())

def DFS():
    if(N == K):
        print(0)
        return
    queue = deque()
    queue.append([N,0])

    while queue:
        a,b = queue.popleft()
       
        # print(a,b,queue)
        if(2*a == K or a-1 == K or a+1 == K):
            print(b+1)
            return
        if(a != 0):
            if([a-1,b+1] not in queue):
                queue.append([a-1,b+1])
            if([2*a,b+1] not in queue):
                queue.append([2*a,b+1])
        if([a+1,b+1] not in queue):
            queue.append([a+1,b+1])


DFS()

시간초과 원인

메모리와 시간을 최소화 하기위해 같은 것을 제거하고 , if(2*a ==k ...): 조건문을 앞에 두었으나 시간초과가 났다.

그럼에도 불구하고 deque는 N,K 차이가 커지면 기하급수적으로 스택이 쌓인다. 실제로 1, 100,000 을 넣고 돌려보니 끝이 나지 않았다. 따라서 방법을 우회해야한다.

정답코드

#숨바꼭질

from collections import deque


MAX = 100000
N,K = map(int,input().split())
dist = [0] * (MAX+1)

def DFS():
    q = deque()
    q.append(N)
    while q:
        x = q.popleft()
        if x == K:
            print(dist[x])
            break

        for j in (x-1,x+1,x*2):
            if(0<=j<=MAX and not dist[j]):
                dist[j] = dist[x]+1
                q.append(j)



DFS()

Q)정답코드와 틀린코드는 구조가 동일한듯보이는데 왜 다를까?

틀린 코드의 deque를 자세히 보면 [4,3] [4,4]가 들어간다. 사실 상 [4,4]는 값이 들어올 필요도 없다. 이런 중복들이 많아지면 계산하는데 시간이 매우 오래 걸리게 된다.

 

 

 

배운점 && 공부방향

 

1. 문제에서 10000이 넘어가는 경우 제한 조건을  활용해야한다.

 

2. 제한 하기 위해 배열의 크기를 활용하는 방법이 있다.

 

3. 배열의 인덱스를 어떤 기준 값으로 활용하자

-> 이문제에서도 값을 두개를 넣지 않고 , 배열의 INDEX를 활용하였다. 

 

4. 반복문을 최소화하는 방향으로 알고리즘을 작성하자.

->정답 풀이는 q를 기준 숫자만

 

5. if문의 조건은 앞부터 체크한다.

 

dist[i]인지부터 체크해서 index out of range 오류가 발생