문제
제한 사항
입출력 예
풀이
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const sol = (input) => {
const [row, column] = input.shift().split(" ").map(Number);
const graph = input.map((e) => e.split(""));
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];
const coinCoordinate = [];
for (let i = 0; i < row; i++) {
for (let j = 0; j < column; j++) {
if (graph[i][j] === "o") {
coinCoordinate.push([i, j]);
}
}
}
const checkDrop = (x, y) => {
if (x < 0 || y < 0 || x >= row || y >= column) return true;
return false;
};
const checkWall = (x, y, index) => {
const [nx, ny] = [x + dx[index], y + dy[index]];
if (graph[nx]) {
if (graph[nx][ny] === "#") return [x, y];
}
return [nx, ny];
};
let min = Number.MAX_SAFE_INTEGER;
const dfs = (cnt, x1, y1, x2, y2) => {
if (cnt >= min) return;
if (cnt > 10) return;
if (checkDrop(x1, y1) && checkDrop(x2, y2)) return;
if (checkDrop(x1, y1) || checkDrop(x2, y2)) {
min = Math.min(min, cnt);
return;
}
for (let i = 0; i < 4; i++) {
const [nx1, ny1] = checkWall(x1, y1, i);
const [nx2, ny2] = checkWall(x2, y2, i);
dfs(cnt + 1, nx1, ny1, nx2, ny2);
}
};
dfs(
0,
coinCoordinate[0][0],
coinCoordinate[0][1],
coinCoordinate[1][0],
coinCoordinate[1][1]
);
return min === Number.MAX_SAFE_INTEGER ? -1 : min;
};
console.log(sol(input));
복습
const sol = (n, m, graph) => {
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];
const coin = [];
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (graph[i][j] === "o") {
coin.push([i, j]);
}
}
}
const checkDrop = (x, y) => {
if (x < 0 || y < 0 || x >= n || y >= n) return true;
else return false;
};
const checkWall = (x, y, index) => {
const [nx, ny] = [x + dx[index], y + dy[index]];
if (graph[nx][ny]) {
if (graph[nx][ny] === "#") return [x, y];
}
return [nx, ny];
};
let min = Number.MAX_SAFE_INTEGER;
const dfs = (cnt, x1, y1, x2, y2) => {
if (cnt > 10) return;
if (checkDrop(x1, y1) && checkDrop(x2, y2)) return;
if (checkDrop(x1, y1) || checkDrop(x2, y2)) {
min = Math.min(min, cnt);
}
for (let i = 0; i < 4; i++) {
const [nx1, ny1] = checkWall(x1, y1, i);
const [nx2, ny2] = checkWall(x2, y2, i);
dfs(cnt + 1, nx1, ny1, nx2, ny2);
}
};
dfs(0, coin[0][0], coin[0][1], coin[1][0], coin[1][1]);
return min === Number.MAX_SAFE_INTEGER ? -1 : min;
};