[JavaScript/DP] 백준 골드 5 : 17070 - 파이프 옮기기 1

https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

---

📌 작성한 코드 1 (DFS - 시간 초과) 

// 17140
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = Number(input.shift());
const board = input.map((str) => str.split(" "));

// 0 : 가로
// 1 : 세로
// 2: 대각선

const dx = [0, 1, 1];
const dy = [1, 0, 1];

const directions = [
    [0, 2],
    [1, 2],
    [0, 1, 2],
];

let count = 0;

const dfs = (x, y, d) => {
    if (x === N - 1 && y === N - 1) {
        count++;
        return;
    }

    const available = Array(3).fill(false);
    for (let i = 0; i < 3; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];

        if (nx >= 0 && nx < N && ny >= 0 && ny < N && board[nx][ny] === "0") {
            if (i === 0 || i === 1) {
                available[i] = [nx, ny, i];
            }
            if (i === 2 && available[0] !== false && available[1] !== false) {
                available[i] = [nx, ny, i];
            }
        }
    }

    if (d === 0) {
        if (available[0] !== false) dfs(...available[0]);
        if (available[2] !== false) dfs(...available[2]);
    }
    if (d === 1) {
        if (available[1] !== false) dfs(...available[1]);
        if (available[2] !== false) dfs(...available[2]);
    }
    if (d === 2) {
        if (available[0] !== false) dfs(...available[0]);
        if (available[1] !== false) dfs(...available[1]);
        if (available[2] !== false) dfs(...available[2]);
    }
};

if (board[N - 1][N - 1] === "1") {
    console.log(0);
} else {
    dfs(0, 1, 0);
    console.log(count);
}

dfs를 이용하여서 가능한 N-1, N-1에 도달하는 모든 경로를 탐색하는 방법이다.

답은 문제없이 구해지지만 시간 초과가 발생한다. (약 60%대) 백준에서 자바스크립트는 참 눈물나는 프로그래밍 언어다. 질문 페이지 읽어보니까 다른 언어들은 dfs 사용하면 어떻게든 풀리긴 한다는데 자바스크립트는 문턱도 밟지 못하게 한다. 이럴 때 슬프다. 

 

간단하게 로직을 설명하자면 

(1) 현재 파이프가 위치한 좌표(파이프의 마지막 좌표)와 파이프가 위치한 방향을 매개변수로 받는다.

(2) 이동할 수 있는 3가지 방향(오른쪽 옆, 아래, 대각선)에 존재하는 좌표를 확인하고, 해당 방향으로 이동할 수 있는지를 확인한다. (available) 

(3) 현재 방향에 따라 이동할 수 있는 방향으로 이동한다. (dfs를 재귀 호출한다)

(4) 도착 지점이 1인 경우를 예외 처리하면 더 빠르게 해결할 수 있다.

 

📌 작성한 코드 2 (DP - 통과) 

// 17140
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = Number(input.shift());
const board = input.map((str) => str.split(" "));

// 0 : 가로
// 1 : 세로
// 2: 대각선
const dp = Array.from({ length: N }, () => Array.from({ length: N }, () => Array(3).fill(0)));
dp[0][1][0] = 1;

for (let j = 2; j < N; j++) {
    if (board[0][j] === "0") dp[0][j][0] = dp[0][j - 1][0];
}

for (let i = 1; i < N; i++) {
    for (let j = 2; j < N; j++) {
        if (board[i][j] === "0") {
            dp[i][j][0] = dp[i][j - 1][0] + dp[i][j - 1][2];
            dp[i][j][1] = dp[i - 1][j][1] + dp[i - 1][j][2];
            if (board[i - 1][j] === "0" && board[i][j - 1] === "0") {
                dp[i][j][2] = dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2];
            }
        }
    }
}

console.log(dp[N - 1][N - 1][0] + dp[N - 1][N - 1][1] + dp[N - 1][N - 1][2]);

📌 설명 

dp를 사용하여 가능한 경로의 개수를 구하는 방법이다. 

`~가능한 경우의 수` 와 같은 문제는 대부분 dp로 풀어서 문제를 읽자마자 dp가 떠올랐지만, bfs/dfs를 사랑하기 때문에 dfs로 먼저 풀었다. 실제 시험에서는 이런일 없도록 하자.. 

 

점화식 세우기 

시작하는 점을 두고 생각하면 복잡하지만, 도착하는 점을 기준으로 생각해보면 쉽게 점화식을 세울 수 있다. 

dp[0][1][0] = 1;

for (let j = 2; j < N; j++) { // 가로 세팅
    if (board[0][j] === "0") dp[0][j][0] = dp[0][j - 1][0];
}

for (let i = 1; i < N; i++) {
    for (let j = 2; j < N; j++) {
        if (board[i][j] === "0") { // 벽이 없는 경우에만
            dp[i][j][0] = dp[i][j - 1][0] + dp[i][j - 1][2];
            dp[i][j][1] = dp[i - 1][j][1] + dp[i - 1][j][2];
            if (board[i - 1][j] === "0" && board[i][j - 1] === "0") { 대각선은 세군데 모두 확인해야함
                dp[i][j][2] = dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2];
            }
        }
    }
}

 

✅ 성공