BOJ [내리막 길]

문제 보기

각 칸에는 해당 위치의 높이가 적혀져 있다.

높이가 낮은 칸으로만 움직일 수 있다.

0,0에서 출발하여 맨 오른쪽 맨 아래칸까지 가는 경로의 수를 구하시오.

풀이

종회형이 던져준 dfs memoization에 대해 공부하다 풀게된 예제이다.

dp로 어떻게 푼다는 말인지 도통 모르겠어서 풀이를 봤다.

재귀 + dp의 개념이 생소해서 풀이를 이해하는 데에도 좀 걸렸다.

내가 이해한 바로는 재귀를 통해 마지막칸 까지 진행한 뒤에 top-down 방식으로

dp를 진행시키는 것이다. 진행하면서 dp에 저장된 칸이면 저장된 값을

dp table에서 불러오고 없으면 top-down 방식이므로 해당 칸에서 진행가능한

칸의 dp 값을 더하는 방식으로 진행한다.

풀이

n,m = list(map(int,input().split()))

board = []

for _ in range(n):
	board.append(list(map(int,input().split())))

c = [[-1]*m for _ in range(n)]

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

def dfs(x,y):
	
	if x == m-1 and y == n-1:
		return 1
	if c[y][x] >= 0:
		return c[y][x]
		
	c[y][x] = 0

	for i in range(4):
		new_x = x + dx[i]
		new_y = y + dy[i]
		if 0<=new_x<m and 0<=new_y<n and board[new_y][new_x] < board[y][x]:
			c[y][x] += dfs(new_x,new_y)

	return c[y][x]

dfs(0,0)
print(c[0][0])