[백준]1520 내리막길

1. 문제요약

(1) dfs,dp문제의 정석

(2) 사이클x

(3) 가능한 경로의 개수(최단경로 아니다!)

 

2. 풀이

(1). 일단 가능한 경로를 모두 찾아야 하기 때문에 dfs로 모두 찾는다.

(2). 초기값은 -1로 지정해준 후, 이때 한번 지나간 곳은 다시갈 필요가 없으므로 0으로 바꿔준다.

(3). 이후 리턴을 받을때 +1씩 해준다

* 설명이 잘되어있는 블로그(단, 초기값이 0으로 되어있어서 시간초과가 난다)

https://wootool.tistory.com/83

[백준][1520번][DP] 내리막길

 

3. 소스코드

(1) 소스코드1

# 이거보셈 https://wootool.tistory.com/83
# 0은 왜 시간초과? https://www.acmicpc.net/board/view/14670
dR=[0,0,-1,1]
dC=[1,-1,0,0]
M,N=map(int,input().split())
L=[]
for i in range(M):
    L.append(list(map(int,input().split())))
visited=[[-1 for j in range(N)] for i in range(M)]
visited[M-1][N-1]=1

def dfs(point):
    '''
    for i in range(M):
        print(visited[i])
    '''
    r=point[0]
    c=point[1]

    if visited[r][c]!=-1:
        return visited[r][c]
    else:
        visited[r][c] = 0

    for k in range(4):
        tempR=r+dR[k]
        tempC=c+dC[k]
        if 0<=tempR<M and 0<=tempC<N and L[r][c]>L[tempR][tempC]:
            visited[r][c]+=dfs([tempR,tempC])
    return visited[r][c]

def main():
    dfs([0,0])
    '''
    for i in range(M):
        print(visited[i])
    '''
    print(visited[0][0])

main()

 

(2) 소스코드2 (3.22 다시풀어봄)

import sys
sys.setrecursionlimit(10**6)

dR=[0,0,-1,1]
dC=[1,-1,0,0]

def dfs(r,c):
    if r==M-1 and c==N-1:
        return 1
    if dp[r][c]!=-1:
        return dp[r][c]

    dp[r][c]=0
    for k in range(4):
        tempR=r+dR[k]
        tempC=c+dC[k]
        if 0<=tempR<M and 0<=tempC<N and L[r][c]>L[tempR][tempC]:
            dp[r][c]+=dfs(tempR,tempC)
    return dp[r][c]



M,N=map(int,input().split())
L=[]
for i in range(M):
    L.append(list(map(int,input().split())))

dp=[[-1 for j in range(N)] for i in range(M)]
print(dfs(0,0))

* m==1 and n==1 일때 dp[0][0] 갱신안되므로 주의!