글 읽기 - [1937] 시간 초과가 나는데 시간 단축에 대한 대응방법을 알고싶습니다.

dbqudgh137 4년 전 0

코드에 대한 코멘트는 주석으로 달아놨습니다.

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

#n, matrix 입력
n = int(input())
matrix = []
for _ in range(n):
    matrix.append(list(map(int, input().split(" "))))

answer = []
#처음부터 끝까지 어떤 자리에서 상하좌우로 자신보다 값이 크면 tmp에 index 저장
for i in range(n):
    for j in range(n):        
        cnt=1
        visit = [[i,j]]
        queue = [[i,j]]
        while queue:
            start = queue.pop(0)
            tmp = []
            for k in range(4):
                ax = start[0]+dx[k]
                ay = start[1]+dy[k]
                if ax>=0 and ax<n and ay>=0 and ay<n:
                    if [ax,ay] not in visit:
                        if matrix[start[0]][start[1]]<matrix[ax][ay]:
                            tmp.append([ax,ay])
            #이동 가능한 index에서 가장 작은 값으로 이동하기 위함
            #그래야 다음 값에서 큰 값을 찾을 확률이 높아진다고 생각함
            if tmp:
                tmp = sorted(tmp, key=lambda k:matrix[k[0]][k[1]])
                queue.append(tmp[0])
                visit.append(tmp[0])
                cnt+=1
        answer.append(cnt)
                    
print(max(answer))
            

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

문제

문제

출처

ICPC

[1937] 시간 초과가 나는데 시간 단축에 대한 대응방법을 알고싶습니다.

dbqudgh137 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말