글 읽기 - 시간 초과 때문에 미칠거 같습니다 도와주세요

kth2642 2년 전 0

40%에서 멈추는데 더 개량할 부분 조언 부탁드립니다

cache[i][j] 는 i행 j열에서 목표점까지 도달할 수 있는 경우의 수입니다

DFS로 골인 지점까지 동서남북 순으로 탐색 후 역으로 계산하는 식으로 코드를 짰습니다

def dfs(m, n):
    if m == M - 1 and n == N - 1:
        return 1
    dm = [0, 1, 0, -1]
    dn = [1, 0, -1, 0]
    # 동서남북 순으로 주변 조회
    for i in range(4):
        if 0 <= m + dm[i] < M and 0 <= n + dn[i] < N:
            if map[m + dm[i]][n + dn[i]] < map[m][n]:
                # 이미 방문한 위치일 경우
                if cache[m + dm[i]][n + dn[i]] != 0:
                    cache[m][n] += cache[m + dm[i]][n + dn[i]]
                # 방문한 적 없는 위치일 경우
                else:
                    cache[m][n] += dfs(m + dm[i], n + dn[i])
    return cache[m][n]

M, N = map(int, input().split())
map = [list(map(int,input().split())) for _ in range(M)]
cache = [[0 for _ in range(N)] for _ in range(M)]
dfs(0,0)
print(cache[0][0])

needsomecash 2년 전 0

미방문칸 cache를 -1로 해야할것 같습니다

도달할수 있는 경우의 수가 0개인 것도 고려해야할거같아요

kth2642 2년 전 0

도달할 수 있는 경우가 0인 경우엔 dfs가 역추적해서 0이 되서 괜찮을 것 같습니다

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

문제

문제

출처

ICPC

시간 초과 때문에 미칠거 같습니다 도와주세요

kth2642 2년 전 0

needsomecash 2년 전 0

kth2642 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말