16932 모양 만들기

문제

N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다.

1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 연결 요소를 모양이라고 부르자. 모양의 크기는 모양에 포함되어 있는 1의 개수이다.

배열의 칸 하나에 들어있는 수를 변경해서 만들 수 있는 모양의 최대 크기를 구해보자.

입력

첫째 줄에 배열의 크기 N과 M이 주어진다. 둘째 줄부터 N개의 줄에는 배열에 들어있는 수가 주어진다.

출력

첫째 줄에 수 하나를 변경해서 만들 수 있는 모양의 최대 크기를 출력한다.

====

문제 분석

우선 초기 gr에 등록되어 있는 1들끼리 묶어준다. 이때 각각의 영역을 고유의 아이디로 등록한 뒤 해당 아이디에 대해 몇개의 1의 갯수가 등록되어 있는지 객체에 기록해둔다.

for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (gr[i][j] !== 1) continue;
            const q = [[i, j]];
            const temp = [[i, j]];
            let cnt = 1;
            num++;
            gr[i][j] = 0;
            while (q.length) {
                const [x, y] = q.shift();
                for (let k = 0; k < 4; k++) {
                    const nx = x + dx[k];
                    const ny = y + dy[k];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                    if (gr[nx][ny] === 0) continue;
                    gr[nx][ny] = 0;
                    cnt++;
                    q.push([nx, ny]);
                    temp.push([nx, ny]);
                }
            }
            for (const [x, y] of temp) {
                gr[x][y] = num;
            }
            rectangle[num] = cnt;
        }
}

이제 그래프에서 1로 바꿀 수 있는 0을 선택한 뒤 해당 지점으로부터 사방면으로 탐색을 하여 연결할 수 있는 영역을 구한다.

이 때 중복되는 영역을 막기 위해 집합에 담아준다.

이후 사방면의 탐색이 종료되면 각 영역별에 담겨진 1의 갯수를 모두 더해주고 0인 지점을 바꿔줬으며로 1을 추가로 더해준다.

마지막으로 해당 합과 answer를 비교한다

for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (gr[i][j] !== 0) continue;
            const s = new Set();
            for (let k = 0; k < 4; 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] !== 0) {
                    s.add(gr[nx][ny]);
                }
            }

            const sum = [...s].reduce((acc, cur) => acc + rectangle[cur], 1);
            answer = Math.max(answer, sum);
        }
}

정답 코드

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

const main = (n, m, gr) => {
    const rectangle = {};
    let num = 10;

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (gr[i][j] !== 1) continue;
            const q = [[i, j]];
            const temp = [[i, j]];
            let cnt = 1;
            num++;
            gr[i][j] = 0;
            while (q.length) {
                const [x, y] = q.shift();
                for (let k = 0; k < 4; k++) {
                    const nx = x + dx[k];
                    const ny = y + dy[k];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                    if (gr[nx][ny] === 0) continue;
                    gr[nx][ny] = 0;
                    cnt++;
                    q.push([nx, ny]);
                    temp.push([nx, ny]);
                }
            }
            for (const [x, y] of temp) {
                gr[x][y] = num;
            }
            rectangle[num] = cnt;
        }
    }
    let answer = Math.max(...Object.entries(rectangle).map((v) => v[1]), 1);

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (gr[i][j] !== 0) continue;
            const s = new Set();
            for (let k = 0; k < 4; 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] !== 0) {
                    s.add(gr[nx][ny]);
                }
            }

            const sum = [...s].reduce((acc, cur) => acc + rectangle[cur], 1);
            answer = Math.max(answer, sum);
        }
    }

    console.log(answer);
};

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 = [];
for (let i = 1; i < n + 1; i++) {
    gr.push(input[i].split(' ').map((v) => +v));
}
main(n, m, gr);