글 읽기 - python 시간초과

gaeuns 2년 전 0

반복문으로 bfs를 구현해서 풀었습니다.

벽 1개는 뚫어도 된다고 해서 1,0을 가리지 않고 queue에 집어넣고 만약에 벽을 한 번이라도 뚫은 적이 있다면 그 이후로 벽은 뚫지 않고 0인 곳만 queue에 집어넣었습니다.

[행,열,벽을 한 번이라도 뚫은 적 있으면 1 아니면 0, count] 이런식으로 데이터를 저장했습니다.

일단 예제 2개는 통과했는데 1~5%에서 시간초과가 뜹니다.

pypy에서도 마찬가지 입니다ㅜ

아래 코드에서 시간을 단축시킬 수 있는 부분이나 알고리즘 상으로 틀린 것이 있으면 알려주세요ㅠㅠ

from collections import deque
import sys
def bfs(input_map,n,m):
    queue = deque([[0,0,0,1]]) #[행, 열, 0or1유무]
    visited = []
    nx = [-1,1,0,0]
    ny = [0,0,-1,1]
    mn = 2001
    while queue:
        current = queue.popleft()
        x = current[0]
        y = current[1]
        visited.append([x,y])
        # if x == n-1 and y == m-1:
        #     mn = min(mn, current[3])
        #     continue
        for i in range(4):
            dx = x + nx[i]
            dy = y + ny[i]
            if (dx >= 0 and dx < n) and (dy >=0 and dy < m) and [dx,dy] not in visited:
                if current[2] == 0:
                    if dx == n-1 and dy == m-1:
                        mn = min(mn,current[3]+1)
                        continue
                    else:
                        queue.append([dx,dy,input_map[dx][dy],current[3]+1])
                        continue
                else:
                    if input_map[dx][dy] == 0:
                        if dx == n-1 and dy == m-1:
                            mn = min(mn, current[3]+1)
                            continue
                        else:
                            queue.append([dx,dy,1,current[3]+1])
                            continue
                    else:
                        continue
            else:
                continue
    if (mn == 2001):
        return -1
    else:
        return mn
 
n, m = sys.stdin.readline().split()
n = int(n)
m = int(m)
input_map = []
for i in range(n):
    input_map.append(list(map(int,sys.stdin.readline().strip())))

print(bfs(input_map,n,m))

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

문제

문제

출처

ICPC

python 시간초과

gaeuns 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말