글 읽기 - [파이썬] 시간초과

ttppggnnss 4년 전 0

시간 초과가 발생하네요

어느 부분에서 시간이 많이 걸리나요?

ans=min(cnt,ans) 부분에서 시간이 많이 초과될까요?

어떻게 고치면 시간을 줄일 수 있을까요?

답변 부탁드립니다 ㅠ

di,dj=[1,-1,0,0],[0,0,1,-1]
def trail(s,b,v):
    global ans
    q=[(s,0,v,1)] # 시작 점, 벽을 뚫었는지, 방문한 점들,길이
    while q:
        i,dig,v,cnt=q.pop()
        if cnt>=ans:
            continue
        if i==(n-1,m-1):
            ans=min(cnt,ans)
            continue
        for k in range(4):
            ni,nj=i[0]+di[k],i[1]+dj[k]
            if -1<ni<n and -1<nj<m and (ni,nj) not in v and b[ni][nj]<1:
                q.append(((ni,nj),dig,v|{(ni,nj)},cnt+1))
            elif -1<ni<n and -1<nj<m and (ni,nj) not in v and b[ni][nj] and dig<1:
                q.append(((ni,nj),1,v|{(ni,nj)},cnt+1))
n,m=map(int,input().split())
b=[[*map(int,input())] for _ in'a'*n]
ans=9**9
trail((0,0),b,{(0,0)})
if ans<9**9:print(ans)
else:print(-1)

dyk777 4년 전 0

python의 list에서 pop()은 맨 앞 원소를 제거한 후 나머지 모든 원소를 일일히 한칸씩 땡겨 오는 것으로 알고 있습니다.

queue나 deque를 사용해보세요.

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

문제

문제

출처

ICPC

[파이썬] 시간초과

ttppggnnss 4년 전 0

dyk777 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말