https://www.acmicpc.net/problem/17070
17070번: 파이프 옮기기 1
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의
www.acmicpc.net
📌 작성한 코드 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];
}
}
}
}
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/DP] 백준 실버 3 : 1904 - 01타일 (1) | 2024.02.28 |
|---|---|
| [JavaScript/DP] 백준 골드 5 : 15486 - 퇴사 2 (2) | 2024.02.28 |
| [JavaScript/DP] 백준 골드 5 : 2011 - 암호 코드 (1) | 2024.02.26 |
| [JavaScript/DP] 백준 실버 1 : 4883 - 삼각 그래프 (0) | 2024.02.26 |
| [JavaScript/BFS] 백준 골드 2 : 11967 - 불켜기 (1) | 2024.02.26 |