[알고리즘] 백준 - 내리막길
다른 사람 풀이
import sys
sys.setrecursionlimit(10**7)
dx = [-1, 0, 0, 1]
dy = [0, 1, -1, 0]
def dfs(y, x):
if y == r-1 and x == c-1:
return 1
result = 0
for i in range(4):
ny, nx = y + dy[i], x + dx[i]
if 0 <= ny < r and 0 <= nx < c and graph[ny][nx] < graph[y][x]:
if dp[ny][nx] >= 0:
# if dp[ny][nx] > 0:
result += dp[ny][nx]
else:
result += dfs(ny, nx)
dp[y][x] = result
return result
r, c = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(r)]
dp = [[-1]*c for _ in range(r)]
# dp = [[0]*c for _ in range(r)]
dp[0][0] = 0
print(dfs(0, 0))
예전에도 다른 사람의 풀이를 보고 풀었더니 풀지 못했다. 이번에 확실히 정리하자.
상하좌우에 현재 자신의 위치보다 낮은 지점이 있을 경우, 해당 지점들이 갖는 경로의 수의 합을 현재 위치에 합한다.
한 번 방문해서 경로의 수를 갖고 있다면 그대로 반환하고, 방문한 점이 없던 지점이라면 새롭게 경로의 수를 구한다.
특이한 점은 현재 코드는 통과가 되지만, 코드 밑에 주석들로 대체하면 시간초과가 난다. 이 부분 생각해 보아야 한다.
자바 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class baekjoon_1520 {
static int R, C;
static int[][] graph, dp;
static int[] dx = new int[]{-1, 0, 0, 1};
static int[] dy = new int[]{0, -1, 1, 0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = br.readLine().split(" ");
R = Integer.parseInt(inputs[0]);
C = Integer.parseInt(inputs[1]);
graph = new int[R][C];
dp = new int[R][C];
for (int i = 0; i < R; i++) {
inputs = br.readLine().split(" ");
for (int j = 0; j < C; j++) {
graph[i][j] = Integer.parseInt(inputs[j]);
}
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
dp[i][j] = -1;
}
}
//dp[i][j] = (i,j)에서 출발하여 (R-1, C-1)까지 가는 방법의 수
System.out.println(dfs(0, 0));
}
private static int dfs(int y, int x) {
if (y == R - 1 && x == C - 1) {
return 1;
}
int ans = 0;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (0 <= ny && ny < R && 0 <= nx && nx < C) {
if (graph[ny][nx] < graph[y][x]) {
if (dp[ny][nx] >= 0) {
ans += dp[ny][nx];
} else {
ans += dfs(ny, nx);
}
}
}
}
dp[y][x] = ans;
return ans;
}
}
Author And Source
이 문제에 관하여([알고리즘] 백준 - 내리막길), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@injoon2019/알고리즘-백준-내리막길저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)