16988 Baaaaaaaaaduk2 (Easy) (자바스크립트)

문제

Baduk2의 룰은 바둑과 거의 유사하지만 양 선수가 돌을 1개씩 번갈아 두는 것이 아니라 2개씩 둔다는 점이 다르다. 서술의 편의를 위해 상하좌우로 인접한 같은 색 돌의 집합을 그룹이라고 하자. 아래의 판에서는 흑의 그룹과 백의 그룹이 각각 3개씩 존재한다.

Baduk2에서는 일반적인 바둑과 동일하게 자신의 돌로 상대방의 그룹을 빈틈없이 에워싸면 갇힌 돌을 죽일 수 있다. 어느 그룹이 빈틈없이 에워싸였다는 것은 그 그룹 내에 빈 칸과 인접해있는 돌이 하나도 없다는 것과 동치이다.

두 빨간 칸 모두 백의 입장에서 착수할 경우 연결된 그룹이 흑돌로 둘러싸이게 되어 원래 바둑의 규칙에서는 백의 입장에서 스스로 잡히는 곳이지만 Baduk2에서는 이와 무관하게 백이 빨간 칸 두 곳에 착수해 8개의 흑돌이 들어있는 그룹의 돌을 죽일 수 있다.

저항군은 AI에게 Baduk2로 도전장을 내밀었고 AI는 의외로 순순히 도전을 받아들였다. 이제 저항군은 2116년 3월 9일, 인류의 자존심을 건 Baduk2 대결을 시작한다. 그리고 당신에게 인류의 승리를 돕기 위해 현재 판 위에서 돌 2개를 두어 상대 돌을 최대한 많이 죽이게끔 하는 프로그램을 작성하는 임무가 주어졌다. 인류의 명예를 걸고 현재 판이 주어질 때 돌 2개를 두어 죽일 수 있는 상대 돌의 최대 갯수를 구하는 프로그램을 작성하자.

입력

첫째 줄에 바둑판의 행의 갯수와 열의 갯수를 나타내는 N(3 ≤ N ≤ 20)과 M(3 ≤ M ≤ 20)이 한 칸의 빈칸을 사이에 두고 주어진다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1, 2이다. 0은 빈 칸, 1은 나의 돌, 2는 상대의 돌을 의미한다. 빈 칸이 2개 이상 존재함과 현재 바둑판에서 양 플레이어 모두 상대방의 돌로 빈틈없이 에워싸인 그룹이 없음이 모두 보장된다.

출력

첫째 줄에 현재 판에서 돌 2개를 두어 죽일 수 있는 상대 돌의 최대 갯수를 출력한다.

 

===

문제 분석 

문제가 이래저래 길지만 1~3문단을 제외하면 결국 빈 공간에 흰 돌 2개를 놓았을 때, 사라질 수 있는 검은 돌의 최대 갯수를 구하는 문제이다.

1. 빈 공간의 좌표 집합 중 2개를 찝어 조합을 구한다. 

const zeroArr = [];
for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
        if (gr[i][j] === 0) {
            zeroArr.push([i, j]);
        }
    }
}

const combinations = [];

const dfs = (idx, com) => {
    if (com.length === 2) {
        combinations.push(com);
        return;
    }
    for (let i = idx + 1; i < zeroArr.length; i++) {
        dfs(i, [...com, i]);
    }
};

dfs(-1, []);

2. 검은 돌의 그룹을 찾고, 동시에 이 검은 돌의 그룹을 사라지지 못하게 하는 빈 공간의 집합을 구한다.

이 때 빈 공간의 좌표가 담긴 집합의 길이가 3이상이라면 어떠한 곳에 놓든 이 검은 돌 그룹은 사라지지 않을 것이므로 패스해준다.

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

const visited = Array.from({ length: n }, () =>
    Array.from({ length: m }, () => false)
);

const blacks = [];
const zeroSet = [];
for (let x = 0; x < n; x++) {
    for (let y = 0; y < m; y++) {
        if (gr[x][y] === 2 && visited[x][y] === false) {
            const q = [[x, y]];
            const coordinates = [[x, y]];
            const s = new Set();	// 빈 공간을 담을 집합
            visited[x][y] = true;

            while (q.length) {
                const [cx, cy] = q.shift();
                for (let i = 0; i < 4; i++) {
                    const nx = cx + dx[i];
                    const ny = cy + dy[i];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                    if (gr[nx][ny] === 0) {
                        s.add(`${nx}-${ny}`);	// 배열로 담으면 중복 처리가 되지 않아 문자열로 저장한 뒤 아래서 좌표화 시킬 것
                    }
                    if (gr[nx][ny] !== 2) continue;
                    if (visited[nx][ny] === true) continue;

                    visited[nx][ny] = true;
                    coordinates.push([nx, ny]);
                    q.push([nx, ny]);
                }
            }
            if (s.size <= 2) {
                blacks.push(coordinates);
                const temp = [...s].map((v) => v.split('-').map(Number));
                zeroSet.push(temp);
            }
        }
    }
}

3. 이제 1번에서 구한 빈 공간 좌표 조합들을 살펴볼 것이다. 검은 돌 그룹을 사라지지 못하게 하는 빈 공간의 좌표들과 비교하면서 빈 공간 좌표의 조합이  검은 돌 그룹을 지울게 할 수 있는 좌표와 완벽히 일치한다면 그 검은 돌은 지워지는 것이므로 해당 idx의 검은 돌 사이즈를 result에 더해준다. 마지막으로 이 result 중 최댓값을 출력하면 된다.

for (const combi of combinations) {
    const [x1, y1] = zeroArr[combi[0]];
    const [x2, y2] = zeroArr[combi[1]];
    let result = 0;
    for (let i = 0; i < zeroSet.length; i++) {
        let cnt = 0;
        for (const [x, y] of zeroSet[i]) {
            if (x === x1 && y === y1) cnt++;
            if (x === x2 && y === y2) cnt++;
        }

        if (cnt === zeroSet[i].length) {
            result += blacks[i].length;
        }
    }
    answer = Math.max(answer, result);
}

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(Number);
const gr = input.slice(1).map((s) => s.split(' ').map(Number));

const zeroArr = [];
for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
        if (gr[i][j] === 0) {
            zeroArr.push([i, j]);
        }
    }
}

const combinations = [];

const dfs = (idx, com) => {
    if (com.length === 2) {
        combinations.push(com);
        return;
    }
    for (let i = idx + 1; i < zeroArr.length; i++) {
        dfs(i, [...com, i]);
    }
};

dfs(-1, []);

let answer = 0;

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

const visited = Array.from({ length: n }, () =>
    Array.from({ length: m }, () => false)
);

const blacks = [];
const zeroSet = [];
for (let x = 0; x < n; x++) {
    for (let y = 0; y < m; y++) {
        if (gr[x][y] === 2 && visited[x][y] === false) {
            const q = [[x, y]];
            const coordinates = [[x, y]];
            const s = new Set();
            visited[x][y] = true;

            while (q.length) {
                const [cx, cy] = q.shift();
                for (let i = 0; i < 4; i++) {
                    const nx = cx + dx[i];
                    const ny = cy + dy[i];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                    if (gr[nx][ny] === 0) {
                        s.add(`${nx}-${ny}`);
                    }
                    if (gr[nx][ny] !== 2) continue;
                    if (visited[nx][ny] === true) continue;

                    visited[nx][ny] = true;
                    coordinates.push([nx, ny]);
                    q.push([nx, ny]);
                }
            }
            if (s.size <= 2) {
                blacks.push(coordinates);
                const temp = [...s].map((v) => v.split('-').map(Number));
                zeroSet.push(temp);
            }
        }
    }
}

for (const combi of combinations) {
    const [x1, y1] = zeroArr[combi[0]];
    const [x2, y2] = zeroArr[combi[1]];
    let result = 0;
    for (let i = 0; i < zeroSet.length; i++) {
        let cnt = 0;
        for (const [x, y] of zeroSet[i]) {
            if (x === x1 && y === y1) cnt++;
            if (x === x2 && y === y2) cnt++;
        }

        if (cnt === zeroSet[i].length) {
            result += blacks[i].length;
        }
    }
    answer = Math.max(answer, result);
}

console.log(answer);