백준 20058 : 마법사 상어와 파이어스톰 - javascript(dfs)

문제 출처 

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

 

정답 풀이 

1. 그러니까, 주어진 grid를 크기에 따라 나누고 

2. 그것을 회전한 후 

3. 조건에 따라 얼음 -1 을 한다. 

4. reduce 활용하여 모든 얼음의 합 

5. dfs를 활용하여 가장 큰 덩어리를 출력

 

 

격자 회전 함수는 아래 블로그에 설명했다. 

https://fordang.tistory.com/352

격자 회전 함수 (90도 회전)

 

정답 코드

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const [N, Q] = input[0].split(' ').map(Number);
const size = 2 ** N;
let grid = input.slice(1, size + 1).map(row => row.split(' ').map(Number));
const Ls = input[size + 1].split(' ').map(Number);

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

// 격자 회전
const rotate = (L) => {
    const subgridSize = 2 ** L;
    const newGrid = Array.from(Array(size), () => Array(size).fill(0));

    for (let r = 0; r < size; r += subgridSize) {
        for (let c = 0; c < size; c += subgridSize) {
            for (let i = 0; i < subgridSize; i++) {
                for (let j = 0; j < subgridSize; j++) {
                    newGrid[r + j][c + subgridSize - i - 1] = grid[r + i][c + j];
                }
            }
        }
    }

    grid = newGrid;
};

// 얼음 줄이기
const reduceIce = () => {
    const toReduce = [];
    for (let r = 0; r < size; r++) {
        for (let c = 0; c < size; c++) {
            if (grid[r][c] === 0) continue;
            let count = 0;
            for (const [dr, dc] of directions) {
                const nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < size && nc >= 0 && nc < size && grid[nr][nc] > 0) {
                    count++;
                }
            }
            if (count < 3) toReduce.push([r, c]);
        }
    }
    toReduce.forEach(([r, c]) => grid[r][c]--);
};

// 가장 큰 얼음 덩어리 크기 구하기 (DFS)
const getLargestIceBlock = () => {
    const visited = Array.from(Array(size), () => Array(size).fill(false));

    // DFS 탐색 함수
    const dfs = (r, c) => {
        const stack = [[r, c]];
        visited[r][c] = true;
        let sizeOfBlock = 1;

        while (stack.length) {
            const [currR, currC] = stack.pop();
            for (const [dr, dc] of directions) {
                const nr = currR + dr, nc = currC + dc;
                if (nr >= 0 && nr < size && nc >= 0 && nc < size && !visited[nr][nc] && grid[nr][nc] > 0) {
                    visited[nr][nc] = true;
                    stack.push([nr, nc]);
                    sizeOfBlock++;
                }
            }
        }
        return sizeOfBlock;
    };

    let maxBlockSize = 0;
    for (let r = 0; r < size; r++) {
        for (let c = 0; c < size; c++) {
            if (grid[r][c] > 0 && !visited[r][c]) {
                maxBlockSize = Math.max(maxBlockSize, dfs(r, c));
            }
        }
    }
    return maxBlockSize;
};

// 파이어스톰 마법 시전
for (const L of Ls) {
    if (L > 0) rotate(L);
    reduceIce();
}

// 남은 얼음의 양
const totalIce = grid.reduce((sum, row) => sum + row.reduce((acc, val) => acc + val, 0), 0);

// 가장 큰 얼음 덩어리 크기
const largestBlock = getLargestIceBlock();

console.log(totalIce);
console.log(largestBlock);