글 읽기 - 파이썬 시간초과 질문드립니다!

eodud9866 3년 전 0

예제들은 아무 이상없이 돌아가는데 시간 초과가 납니다. 어떻게 해결해야 할까요..

#미로탐색
import sys
from collections import deque
r = sys.stdin.readline

def bfs(N,M,MAP):
    #상우하
    dx = [-1, 0, 1]
    dy = [0, 1, 0]

    queue = deque()
    queue.append([0,0])
    time = 1

    while True:
        time += 1
        for _ in range(len(queue)):
            x,y = queue.popleft()

            for i in range(3):
                nx = x + dx[i]
                ny = y + dy[i]
                
                if (0<=nx<N) and (0<=ny<M):
                    
                    if MAP[nx][ny] == 1:
                        MAP[nx][ny] = 0
                        queue.append([nx,ny])
                        if nx==(N-1) and ny==(M-1):
                            return time 

N,M = map(int,r().split())
MAP = []
for i in range(N):
    row = list(map(int,input()))
    MAP.append(row)
print(bfs(N,M,MAP))

kk0640 3년 전 0

이미 지나갔던 곳들에 대해서 방문 여부를 체크해 주지 않으셧습니다.

때문에 이미 방문한 곳들도 다시 가고있어서 시간초과가 난 것으로 보입니다.

eodud9866 3년 전 0

kk0640님

답변감사합니다!

혹시 방문여부라는 것이 무슨 의미인가요? 1인 부분으로만 방문하고 0으로 바꿔주고 있는데 이미 지나갔던 곳은 다시 방문 안하게 되는게 맞지 않나요?

kk0640 3년 전 0

짜신 코드에서는 queue 의 길이만큼 도는데 예제 1번 에서 보면 (0,0)은 이미 출발한 위치임에도 불구하고 (1,0)에서 다음 곳을 찾을때 (0,0) 와 (2,0)을 모두 찾습니다. 찾지 않아도 되는 곳을 미리 체크해서 보지 않으면 해결 될 것 같습니다.

kk0640 3년 전 0

또한 움직이는 방향을 보시면 상하우로만 움직이시는데 그런 이유가 있나요? 상하좌우로 이동하셔야할 것 같습니다.

kk0640 3년 전 0

방문에 대해서 는 따로 생각안하시고 이동방향만 수정해주시면 정답으로 처리되십니다

eodud9866 3년 전 0

감사합니다!

방문했던 곳 체크는 의아했는데 괜찮았던 것 같습니다.

그런데 방향은 좌를 빼먹은 것이 잘못됐다는 것은 이해했습니다. 그렇다면 시간초과가 아닌 틀렸습니다가 나오는게 맞지 않나요..??ㅠㅠ

어렵네요 정말 감사합니다!!

kk0640 3년 전 0

아마도 while문을 벗어나지 못해서 시간초과 나올꺼예요

eodud9866 3년 전 0

헉 다른 반례가 있나보네요

ㅜㅜ 감사합니다.

댓글을 작성하려면 로그인해야 합니다.