글 읽기 - 어디서 시간초과가 나는 건지 잘 모르겠습니다ㅠㅠ

tlsrbwls999 2년 전 0

3차원배열로 풀어서 시간초과를 해결했다고 생각했는데 아니네여 ㅠㅠ 어디서 시간초과가 발생하는 걸까요 ㅠㅠ

from collections import deque
import sys
n,m=map(int,sys.stdin.readline().split())
graph=[]

for _ in range(n):
    graph.append(list(sys.stdin.readline()))

visited=[[[0]*2 for _ in range(m)] for _ in range(n)]

pos=deque()
pos.append((0,0,1))
visited[0][0][1]=1


dx=[-1,1,0,0]
dy=[0,0,-1,1]
test=False
num=0

while pos:
    x,y,w = pos.popleft()
    if x==n-1 and y==m-1:
        test=True
        break
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if 0<=nx<n and 0<=ny<m:
            if graph[nx][ny] == '1' and w == 1:
                visited[nx][ny][0] = visited[x][y][1] + 1
                pos.append((nx, ny, 0))
            elif graph[nx][ny] == '0' and visited[nx][ny][w] == 0:
                visited[nx][ny][w] = visited[x][y][w] + 1
                pos.append((nx, ny, w))


if test:
    print(visited[n-1][m-1][w])
else:
    print(-1)

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

문제

문제

출처

ICPC

어디서 시간초과가 나는 건지 잘 모르겠습니다ㅠㅠ

tlsrbwls999 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말