[baekjoon] 1520 내리막 길 (Javascript,Python)

1520번: 내리막 길 (acmicpc.net)

1520번: 내리막 길

---

알고리즘 : dfs, dp

 

초기에 문제를 구현했는데 정상적으로 구현이 되었다.

하지만, 시간초과가 발생해서 다른 방법을 찾았다!

이런 문제는 처음으로 구현방법을 찾지 못해서 고민하다가 검색을 했고, dp 메모리제이션이라는 방법을 찾아서 적용해 볼 수 있었다.

 

 

- Javascript 시간초과 코드

function solution() {
  let input = require("fs")
    .readFileSync("input.txt") //"/dev/stdin"
    .toString()
    .split("\n")
    .map((val) => val.trim());

  let [n, m] = input
    .shift()
    .split(" ")
    .map((v) => +v);
  let graph = input.map((v) => v.split(" ").map((val) => +val));

  // 0,0 -> n-1,m-1 까지 높이가 나보다(지금위치보다) 낮은 곳으로 이동하면서 가는 루트의 개수

  let ans = 0;

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

  const dfs = (x, y, vis) => {
    vis[x][y] = 1;
    for (let dir = 0; dir < 4; dir++) {
      let nx = x + dx[dir];
      let ny = y + dy[dir];
      if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if (vis[nx][ny] === 1 || graph[nx][ny] >= graph[x][y]) continue;
      if (nx === n - 1 && ny === m - 1) {
        ans++;
        return;
      }
      vis[nx][ny] = 1;
      dfs(nx, ny, vis);
      vis[nx][ny] = 0;
    }
  };

  let vis = new Array(n).fill().map((_) => new Array(m).fill(0));
  dfs(0, 0, vis);
  console.log(ans);
}

solution();

 

- dp 메모리제이션을 적용한 코드

function solution() {
  let input = require("fs")
    .readFileSync("input.txt") //"/dev/stdin"
    .toString()
    .split("\n")
    .map((val) => val.trim());

  let [n, m] = input
    .shift()
    .split(" ")
    .map((v) => +v);
  let graph = input.map((v) => v.split(" ").map((val) => +val));

  // 0,0 -> n-1,m-1 까지 높이가 나보다(지금위치보다) 낮은 곳으로 이동하면서 가는 루트의 개수

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

  let dp = new Array(n).fill().map((_) => new Array(m).fill(-1));
  dp[n - 1][m - 1] = 1;

  const dfs = (x, y) => {
    if (dp[x][y] !== -1) return dp[x][y];

    dp[x][y] = 0;

    for (let dir = 0; dir < 4; dir++) {
      let nx = x + dx[dir];
      let ny = y + dy[dir];
      if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if (graph[nx][ny] >= graph[x][y]) continue;

      dp[x][y] += dfs(nx, ny);
    }

    return dp[x][y];
  };

  console.log(dfs(0, 0));
}

solution();

 

- Python

import sys

sys.stdin = open("baekjoon/1520/input.txt","r")
input = sys.stdin.readline

n,m = map(int,input().rstrip().split())
graph = [list(map(int,input().rstrip().split())) for _ in range(n)]

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

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

def dfs (x,y):
    if dp[x][y]!=-1:
        return dp[x][y]
    
    dp[x][y]=0
    for dir in range(4):
        nx = x+dx[dir]
        ny = y+dy[dir]
        if(0<=nx<n and 0<=ny<m and graph[nx][ny]<graph[x][y]):
            dp[x][y] += dfs(nx,ny)
        
    
    return dp[x][y]

print(dfs(0,0))