[JavaScript] 백준 골드 5 : 20165 - 인내의 도미노 장인 호석

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

20165번: 인내의 도미노 장인 호석

---

📌 작성한 코드 

// 20165
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, M, R] = input.shift().split(" ").map(Number);

const board = [];
for (let i = 0; i < N; i++) {
    board.push(input[i].split(" ").map(Number));
}

const attack = [];
const defence = [];

for (let i = N; i < N + R * 2; i += 2) {
    attack.push(input[i].split(" ").map((val) => (isNaN(val) ? val : Number(val) - 1)));
    defence.push(input[i + 1].split(" ").map((val) => Number(val) - 1));
}

const directions = {
    E: [0, 1],
    W: [0, -1],
    S: [1, 0],
    N: [-1, 0],
};

const visited = Array.from({ length: N }, () => new Array(M).fill("S"));

let totalScore = 0;

const recursive = (x, y, d) => {
    const [dx, dy] = directions[d];
    const count = board[x][y];

    let nx = x;
    let ny = y;

    for (let j = 0; j < count; j++) {
        if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
        if (visited[nx][ny] === "S") {
            visited[nx][ny] = "F";
            totalScore++;
            recursive(nx, ny, d);
        }

        nx += dx;
        ny += dy;
    }
};

for (let i = 0; i < R; i++) {
    const [x, y, d] = attack[i];
    const [a, b] = defence[i];

    recursive(x, y, d);
    visited[a][b] = "S";
}

console.log(totalScore);
visited.forEach((val) => {
    console.log(val.join(" "));
});

 

📌 설명 

공격자는 도미노를 넘어트리고, 수비자는 도미노를 다시 세울 수 있는 게임에서 공격자가 얻은 점수과 게임 결과를 알아내는 문제이다. 

 

도미노 게임의 규칙 

1. 공격자는 도미노를 동서남북 중 한 방향을 선택하여 넘어트릴 수 있다.

2. 도미노는 해당 방향에 위치한 도미노의 높이 -1 개수 만큼 추가로 도미노를 넘어트린다. (본인 포함하면 높이 만큼)

3. 도미노는 연쇄적으로 넘어질 수 있다.

4. 수비자는 각 라운드마다 한개의 도미노를 다시 세울 수 있다.

 

문제를 풀기 전 생각해야 할 점

1. 도미노가 연쇄적으로 넘어질 수 있으므로 우리는 재귀를 사용해서, 넘어진 도미노가 다른 도미노에도 영향을 미칠 수 있게 해야한다.

2. 좌표를 사용할 때 0이 아니라 1부터 주어지므로 좌표에 -1해서 사용해야 한다.

 

도미노 넘어트리기

const visited = Array.from({ length: N }, () => new Array(M).fill("S")); // 넘어진 상황
let totalScore = 0; // 공격자가 넘어트린 개수

const recursive = (x, y, d) => {
    const [dx, dy] = directions[d]; // 어느 방향으로 넘어트릴 것인지 받아오기
    const count = board[x][y]; // 도미노를 넘어트릴 개수(본인 포함)

    let nx = x;
    let ny = y;

    for (let j = 0; j < count; j++) {
        if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue; // 범위 넘어가면 넘어트리지 못함
        if (visited[nx][ny] === "S") { // 아직 넘어지지 않았다면
            visited[nx][ny] = "F"; // 넘어트리기
            totalScore++;
            recursive(nx, ny, d); // 도미노 넘어트리는 것의 연쇄작용
        }

        nx += dx; // 본인 포함이라서 넘어트리고 나서 개수를 증가시킨다
        ny += dy;
    }
};

 

✅ 성공