16957 체스판 위의 공

문제

크기가 R×C인 체스판이 있고, 체스판의 각 칸에는 정수가 하나씩 적혀있다. 체스판에 적혀있는 정수는 모두 서로 다르다.

체스판의 각 칸 위에 공을 하나씩 놓는다. 이제 공은 다음과 같은 규칙에 의해서 자동으로 움직인다.

• 인접한 8방향 (가로, 세로, 대각선)에 적힌 모든 정수가 현재 칸에 적힌 수보다 크면 이동을 멈춘다.
• 그 외의 경우에는 가장 작은 정수가 있는 칸으로 공이 이동한다.

공의 크기는 매우 작아서, 체스판의 한 칸 위에 여러 개의 공이 있을 수 있다. 체스판의 상태가 주어진다. 공이 더 이상 움직이지 않을 때, 각 칸에 공이 몇 개 있는지 구해보자.

입력

첫째 줄에 체스판의 크기 R, C가 주어진다. 둘째 줄부터 R개의 줄에 체스판에 적혀있는 정수가 주어진다.

출력

총 R개의 줄에 걸쳐서 체스판에 적힌 정수를 출력한다.

====

문제 분석

특정 좌표를 기준으로 주위 8개의 점 중에서 가장 작은 값과 체스를 옮기는 문제이다.

만약 시뮬레이션 구현 방식으로 푼다면 우선 모든 좌표들을 탐색하면서 주위 점들 중 가장 작은 값을 가진 좌표를 담아두어서 기록해두고

무한 반복을 통해서 체스를 계속 옮겨가고 체스의 움직임이 없을 경우 게임을 멈추고 정답을 출력하면 된다.

하지마 그럴 경우 전체 탐색을 지속적으로 해야하므로 불필요한 연산이 발생한다.

이것을 최적화하기 위해 각 좌표별로 가장 작은 값을 가지는 좌표를 최종적으로 옮기게 될 좌표를 기록해두면 된다. 

이것을 위해 가장 작은 좌표를 찾는 findParent 함수와 이것을 합체하는 union 함수를 만들어준다.

    const parent = Array.from({ length: n }, (_, i) =>
        Array.from({ length: m }, (_, j) => [i, j])
    );
    const findParent = (cx, cy) => {
        const [px, py] = parent[cx][cy];
        if (px !== cx || py !== cy) {
            return findParent(px, py);
        }
        return [cx, cy];
    };

    const union = (x, y, x1, y1) => {
        const parent1 = findParent(x, y);
        const parent2 = findParent(x1, y1);
        if (parent1[0] !== parent2[0] || parent1[1] !== parent2[1]) {
            parent[parent1[0]][parent1[1]] = parent2;
        }
    };

이제 전체 탐색을 하면서 findParent와 union을 통해 특정 점을 기준으로 가장 작은 값을 가지는 최종 좌표를 기록한다.

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            let MIN = gr[i][j];
            let [mx, my] = [i, j];
            for (let k = 0; k < 8; k++) {
                const nx = i + dx[k];
                const ny = j + dy[k];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if (gr[nx][ny] < MIN) {
                    MIN = gr[nx][ny];
                    mx = nx;
                    my = ny;
                }
            }

            if (mx !== i || my !== j) {
                union(i, j, mx, my);
            }
        }
    }

이를 토대로 만들어진 좌표 그래프를 통해 체스를 옮기기만 하면 된다.

나는 최종 표를 만드는 과정을 bfs로 하면서 불필요한 연산을 너무 많이 했었다.

최종 코드

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

const main = (n, m, gr) => {
    const horses = Array.from({ length: n }, () =>
        Array.from({ length: m }, () => 1)
    );
    const parent = Array.from({ length: n }, (_, i) =>
        Array.from({ length: m }, (_, j) => [i, j])
    );
    const findParent = (cx, cy) => {
        const [px, py] = parent[cx][cy];
        if (px !== cx || py !== cy) {
            return findParent(px, py);
        }
        return [cx, cy];
    };

    const union = (x, y, x1, y1) => {
        const parent1 = findParent(x, y);
        const parent2 = findParent(x1, y1);
        if (parent1[0] !== parent2[0] || parent1[1] !== parent2[1]) {
            parent[parent1[0]][parent1[1]] = parent2;
        }
    };

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            let MIN = gr[i][j];
            let [mx, my] = [i, j];
            for (let k = 0; k < 8; k++) {
                const nx = i + dx[k];
                const ny = j + dy[k];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if (gr[nx][ny] < MIN) {
                    MIN = gr[nx][ny];
                    mx = nx;
                    my = ny;
                }
            }

            if (mx !== i || my !== j) {
                union(i, j, mx, my);
            }
        }
    }

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            const [px, py] = findParent(i, j);
            if (px === i && py === j) continue;
            const num = horses[i][j];

            horses[i][j] -= num;
            horses[px][py] += num;
        }
    }

    console.log(horses.map((v) => v.join(' ')).join('\n'));
};

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, m] = input[0].split(' ').map((v) => +v);
const gr = input.slice(1).map((s) => s.split(' ').map((v) => +v));

main(n, m, gr);