[알고리즘][파이썬]1697-숨바꼭질 오류 해결(feat.chat.gpt)

문제

백준 1697-숨바꼭질

1697번: 숨바꼭질

 

오류

숨바꼭질 문제 코드를 다음과 같이 풀었다.

결론은 시간초과로 인한 실패...ㅠㅠ

계속 보다가 다른 분들의 코들 봤는데 알고리즘이 유사해 원인을 찾기 어려워

 ChatGPT에게 물어봤다....🌟

 

 

나:

백준 1697 숨바꼭질 문제를 푸는데 시간초과로 실패했어
내 코드를 보고 원인을 찾아줘 아래는 내가 제출한 코드야~

import sys
from collections import deque
n,k = map(int,sys.stdin.readline().strip().split())

def bfs(v):
    visited=[v]
    q= deque()
    q.append((v,0))

    while(q):
        v,c = q.popleft()
        if(v==k):
            return c
        for i in range(3):
            if(i==0):nv =v +1
            elif(i==1):nv = v -1
            else:nv = v*2
            if(0<= nv <= 100000 and nv not in visited):
                visited.append(nv)
                q.append((nv,c+1))
               

print(bfs(n))

 

 

ChatGPT:

주어진 코드를 살펴보니, 시간 초과로 실패하는 이유는 다음과 같습니다:

-visited 리스트를 사용하여 방문한 노드를 저장하고 있지만, visited 리스트를 탐색하는 부분에서 선형 탐색을 수행하고 있습니다. 이로 인해 visited 리스트를 반복적으로 탐색해야 하므로 시간이 오래 걸립니다. 대신에 visited 리스트 대신 visited 집합(Set)을 사용하여 노드의 방문 여부를 빠르게 확인할 수 있습니다.

아래는 수정된 코드입니다:
수정된 코드에서는 visited를 set으로 선언하여 빠른 탐색이 가능하도록 하였으며, v == k일 때마다 visited리스트를 출력하는 부분을 삭제하였습니다. 이렇게 수정하면 시간 초과 문제를 해결할 수 있을 것입니다.

import sys
from collections import deque

n, k = map(int, sys.stdin.readline().strip().split())

def bfs(v):
    visited = set()
    q = deque()
    q.append((v, 0))
    visited.add(v)

    while q:
        v, c = q.popleft()
        if v == k:
            return c
        for i in range(3):
            if i == 0:
                nv = v + 1
            elif i == 1:
                nv = v - 1
            else:
                nv = v * 2
            if 0 <= nv <= 100000 and nv not in visited:
                visited.add(nv)
                q.append((nv, c + 1))

print(bfs(n))

 

 ChatGPT를 통해 알게 된 문제 원인: visited 변수를 리스트로 두어 nv not in visited코드를 실행할 때 리스트를 탐색하게 되고 이때 시간이 오래 걸리게 된 것이다.  이를 해결하기 위해 gpt가 제시한 방법은 set() 집합으로 visited를 처리하는 것이었다. 리스트에서 해당 값이 있는지 확인을 하게 될 때 시간이 오래 걸릴 수 있다는 것을 생각하고 코드를 작성해야겠다.

 

ChatGPT짱👍