글 읽기 - 방문 처리하는 코드 위치에 따른 시간초과가 나는 이유가 무엇인지요?

thetest1 2년 전 0

분명 예제 전부 맞았고 반례도 다 찾아보진 않았으나 이곳 게시물 반례들은 찾아서 넣었더니 통과되었습니다. 또한 무한루프 걸린다는 예시들이랑 N=20인 경우도 이 곳 질문에서 예시를 찾아서 다른 사람들 코드와 비교했을 때 시간초과가 안 나는 것을 확인하였습니다.

하지만 제출만 하면 25퍼에서 계속 시간초과가 나는 것을 해결하지 못 했었습니다.

그런데 다른 분의 글을 보니 저와 같은 증상을 겪고 있었고 그 해결법은 큐에서 꺼낸 다음에 방문 처리를 하면 시간초과가 나는 것이고 큐에 넣을 때 방문 처리하면 시간초과가 나지 않는 것이었습니다.

왜 이러한 결과가 나는 것일 까요?

어차피 큐에서 꺼낼 때 방문 처리하나 큐에 넣을 때 방문 처리하나 코드가 실행되는 건 변함없고 코드도 1줄 뿐인데 왜 이런 차이가 나는지 이해가 잘 안됩니다.

N=int(input())
M=[[*map(int,input().split())]for _ in range(N)]
W=[[1]*N for _ in range(N)]
s=2;p=c=k=0
for i in range(N):
    for j in range(N):
        if 8<M[i][j]:p=(i,j,0);M[i][j]=0;W[i][j]=0
t=[p]
f=[]
while t:
    o=[]
    n=N*N
    for v in t:
        u,v,d=v
        #W[u][v]=0 원래는 여기서 방문처리했는데 시간초과 남
        for a,b in [[1,0],[-1,0],[0,1],[0,-1]]:
            if -1<u+a<N and -1<v+b<N and W[u+a][v+b] and M[u+a][v+b]<=s:
                if 0<M[u+a][v+b]<s:f+=[(u+a,v+b,d+1)];n=d
                if d+1<=n:o+=[(u+a,v+b,d+1)];W[u+a][v+b]=0 #여기서 방문처리하니 시간초과 안 남

    if f:
        f.sort()
        u,v,d=f[0]
        M[u][v]=0
        c+=d
        k+=1
        if k==s:s+=1;k=0
        o=[(u,v,0)]
        f=[]
        W=[[1]*N for _ in range(N)]
    l=True
    for i in range(N):
        for v in M[i]:
            if 0<v<s:l=False
    if l:break
    t=o
print(c)

djm03178 2년 전 2

큐에서 뺀 뒤에 처리하면, 동시에 여러 칸에서 같은 칸을 방문하는 경우에 그 모두가 큐에 들어가게 되고, 거기서 나온 칸이 방문하는 칸들도 모두 그 횟수만큼 + 다른 칸에서 온 횟수만큼 중복되어 큐에 들어가고... 하는 것을 반복하게 됩니다.

thetest1 2년 전 0

큐에 들어갈 땐 중복될 수 있다는 걸 놓친 부분이었군요

감사합니다

그냥 방문 처리했으니 중복되진 않겠지하는 막역한 생각을 했네요

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

문제

문제

출처

ICPC

방문 처리하는 코드 위치에 따른 시간초과가 나는 이유가 무엇인지요?

thetest1 2년 전 0

djm03178 2년 전 2

thetest1 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말