알고리즘 유형 : DP(Dynamic Programming)
풀이 참고 없이 스스로 풀었나요? : X
https://www.acmicpc.net/problem/1520
소스 코드(node.js)
"use strict";
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin","utf-8").trim().split("\n");
const [M, N] = input[0].split(" ").map(Number);
const dRow = [1, 0, -1, 0];
const dCol = [0, 1, 0, -1];
const board = [];
for (let i=1; i<M+1; i++){
board.push(input[i].split(" ").map(Number));
}
// 단순 DFS로 풀 때의 같은 노드 중복 재귀 호출을 피하기 위해, DP 메모이제이션 활용
// 어떤 노드의 H는 상하좌우 값 작은 노드들의 H들의 합임. 부분 문제 정의
// 중복 호출을 피하기 위해, 방문을 안 한 노드의 위치는 -1을 가지고,
// 방문을 한 노드는 연산 결과, 0이나 그 이상의 H를 가짐
// H가 0이라는 것은 그 노드 상하좌우에 내려갈 길이 없거나,
// 내려갔는데 그 내려간 노드의 H가 모두 0인 경우이므로 즉
// 마지막 노드까지 도달할 수 없는 경우라는 것이다.
const DP = [];
for (let i=0; i<M; i++){
DP.push([]);
for (let j=0; j<N; j++){
DP[i].push(-1);
}
}
function DFS(row, col){
if (row === M-1 & col === N-1){
return 1;
}
if (DP[row][col] != -1){
return DP[row][col];
}
let H = 0;
for (let i=0; i<4; i++){
let nRow = row + dRow[i];
let nCol = col + dCol[i];
if (nRow >= 0 & nRow < M & nCol >= 0 % nCol < N){
if (board[nRow][nCol] < board[row][col]){
H += DFS(nRow, nCol);
}
}
}
DP[row][col] = H;
return H;
}
console.log(DFS(0, 0));풀이 요약
-
DFS에 DP 개념을 적용하여 푼다. 부분 문제를 정의해보면
(x, y)에서 목적지 좌표까지 가는 경로의 수를 DP(x, y) 라고 하면, DP(x, y) = DP(x-1, y) + DP(x+1, y) + DP(x, y-1) + DP(x, y+1) (단, x-1, x+1, y-1, y+1이 board의 범위 안에 있는 인덱스이고, 내리막길일 때) 이다.
이를 구현하기 위해, (0, 0)부터 DFS로 마지막 노드까지 탐색한다. DP 부분 문제 개념대로 자식 노드를 호출해나가고, 메모이제이션을 활용해 노드 중복 탐색을 피한다.
-
함수 DFS는 좌표가 (row, col)인 노드에서 마지막 노드까지 가는 경로의 수를 리턴하는 함수이다.
아까 설명한 DP 개념대로, 다음 인접 노드로의 탐색은 상하좌우 방향이고, 현재 노드보다 값이 작아야한다는게 탐색 조건이다.
그렇게 상하좌우를 조건에 맞는 것만 재귀 호출하고, 리턴값들을 싹다 더한 것이 현재 노드에서 마지막 노드까지의 경로 수 H이다.
H는 0이거나 그 이상의 수일 수 있다.
다만, 4방향 DFS 탐색 이전에, 종료값과 메모이제이션으로 탐색 없이 바로 리턴해줄 수 있는 경우를 작성해줘야한다.
현재 탐색중인 노드가 마지막 노드인 경우, 종료값 1을 리턴해준다. 마지막 노드 이전의 어떤 노드에서 4방향 재귀에서 마지막 노드를 호출했을 때, 1을 리턴해주는게 맞기 때문이다.
참고로 DP는 싹 다 -1로 초기화해놓는다. 방문을 하지 않았다는 뜻이다.
그리고 만약 현재 노드의 H 값이 이미 구해져있다면, 즉 -1이 아니고 0이나 그 이상의 값이라면, 그냥 그걸 리턴하면 된다.
이 두 개의 조건문이 둘다 아니라면, 그 때는 현재 노드가 마지막 노드도 아닌데다가 처음으로 방문하는 노드라는 뜻이다. 그러므로 4방향 DFS 탐색을 실행한다.
4방향 탐색 후, 이 노드는 탐색을 한 것이므로 DP에 H 값을 넣어준 후, H를 리턴한다.
넣어준 DP값은, 나중에 어떤 노드가 이 노드를 또 호출했을 때, 이 노드에서 또 4방향 재귀를 하지말고, 이미 구해놨던 H를 바로 리턴해줘서 시간복잡도를 줄이는데 활용할 수 있다. 메모이제이션 기법이다.
- DFS(0, 0)의 리턴 값을 출력해주자!
배운 점, 어려웠던 점
- 처음에 풀 때 DFS로 마지막까지 탐색 후, 마지막 노드가 호출됐을 때 count += 1을 해주는 방식으로 풀었는데, 이건 DP를 적용한 풀이가 아닌데다가 시간 초과가 났다.
- DFS랑 DP를 어떻게 같이 써야할지 못 떠올렸다... DFS에 DP가 접목되는 형태를 많이 경험해볼 필요를 느꼈다. 좀 쉽게 설명해보자면.. 이 문제는 재귀 구조, 즉 top-down 방식의 DP 풀이인데, 그 재귀 구조가 바로 DFS인 형태이다.
