[백준] 1520번 - 내리막 길 (C++, 파이썬) 문제 및 풀이

문제) 백준 - 동적 계획법 (Dynamic Programming) - 내리막 길

-> www.acmicpc.net/problem/1520

1520번: 내리막 길

 

각 지점까지 이동할 수 있는 경로의 수를 저장한 2차원 리스트(dist)에 메모이제이션을 적용한다. dist 리스트의 초기값을 -1로 선언해 방문 여부를 판단한다. 각 지점까지 이동할 수 있는 경우의 수는 dfs를 이용하여 경로가 겹치는 지점에서 서로의 경로 수를 합친다. 

 

 

Python 소스 코드)

 

	def dfs(x, y):
	# 기저 사례
	if x == 0 and y == 0:
	return 1
	if dist[x][y] == -1:
	dist[x][y] = 0
	for i in range(4):
	nx, ny = x + dx[i], y + dy[i]
	if 0 <= nx < m and 0 <= ny < n:
	if graph[x][y] < graph[nx][ny]:
	dist[x][y] += dfs(nx, ny)
	return dist[x][y]

view raw 1520.py hosted with ❤ by GitHub

C++ 소스 코드)

 

	int m, n;
	int board[MAX][MAX];
	int cache[MAX][MAX];
	int dfs(int x, int y) {
	if (x == 0 && y == 0) return 1;
	int& ret = cache[x][y];
	if (ret != -1) return ret;
	ret = 0;
	for (int i = 0; i < 4; ++i) {
	int nx = x + Dir[i].first;
	int ny = y + Dir[i].second;
	if (0 <= nx && nx < m && 0 <= ny && ny < n)
	if(board[nx][ny] > board[x][y])
	ret += dfs(nx, ny);
	}
	return ret;
	}

view raw 1520.cpp hosted with ❤ by GitHub

 

Python Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/1520_%EB%82%B4%EB%A6%AC%EB%A7%89%20%EA%B8%B8.py

GitHub - Chocochip101/BOJ_Solution

 

C++ Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/1520_%EB%82%B4%EB%A6%AC%EB%A7%89%20%EA%B8%B8.cpp

GitHub - Chocochip101/BOJ_Solution