[백준/G4] 14502 연구소

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

python

115076kb 500ms PyPy3

deepcopy 중요

import sys, copy

input = sys.stdin.readline

from itertools import combinations
from collections import deque


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


def bfs(i, j, visited, arr):
    visited[i][j] = True
    q = deque()
    q.append((i, j))
    # 위 대신에
    # q = deque([(i, j)]) 해도 별 차이는 없는듯...?

    while q:
        x, y = q.popleft()

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if not (0 <= nx < N and 0 <= ny < M):
                continue

            if arr[nx][ny] == 0 and not visited[nx][ny]:
                q.append((nx, ny))
                visited[nx][ny] = True
                arr[nx][ny] = 2


N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

empty = []
for i in range(N):
    for j in range(M):
        if arr[i][j] == 0:
            empty.append([i, j])


ans = 0

for comb in combinations(empty, 3):
    # check_arr = copy.deepcopy(arr)
    # 아래와 같이 하면 시간이 반으로 줄음
    check_arr = [row[:] for row in arr]
    cnt = 0

    for i, j in comb:
        # check_arr에 조합의 수에 해당하는 벽 세우기
        check_arr[i][j] = 1

    visited = [[False] * M for _ in range(N)]

    for i in range(N):
        for j in range(M):
            # check_arr의 바이러스를 찾아서 bfs로 퍼지도록
            # 단, 2로 바꾼 후 다시 중복체크 되지 않도록 visited로 조건을 한번 더 걸어줌
            if check_arr[i][j] == 2 and not visited[i][j]:
                bfs(i, j, visited, check_arr)

    for i in range(N):
        for j in range(M):
            # 안전구역 카운트
            if check_arr[i][j] == 0:
                cnt += 1

    ans = max(ans, cnt)

print(ans)

JS

python과 달리 combination이 내장되어 있지 않으므로 직접 구현해야함

54384ks 600ms node.js

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

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

function bfs(i, j, visited, arr) {
    visited[i][j] = true;
    const q = [];
    q.push([i, j]);

    while (q.length > 0) {
        const [x, y] = q.shift();

        for (let d = 0; d < 4; d++) {
            const nx = x + dx[d];
            const ny = y + dy[d];

            if (!(0 <= nx && nx < N && 0 <= ny && ny < M)) {
                continue;
            }

            if (arr[nx][ny] === 0 && !visited[nx][ny]) {
                q.push([nx, ny]);
                visited[nx][ny] = true;
                arr[nx][ny] = 2;
            }
        }
    }
}

const [N, M] = input[0].split(" ").map(Number);
const arr = input.slice(1).map(line => line.split(" ").map(Number));

let empty = [];

for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
        if (arr[i][j] === 0) {
            empty.push([i, j]);
        }
    }
}

let ans = 0;

const getCombination = (arr, n) => {
    if (n === 1) return arr.map(el => [el]);
    const result = [];

    arr.forEach((fixed, idx, origin) => {
        const rest = origin.slice(idx + 1);
        const combis = getCombination(rest, n - 1);
        const attached = combis.map(combi => [fixed, ...combi]);
        result.push(...attached);
    });

    return result;
}

const combinations = getCombination(empty, 3);

for (let comb of combinations) {
	// 깊은 복사
    let checkArr = arr.map(row => [...row]);
    let cnt = 0;

    for (let [i, j] of comb) {
        checkArr[i][j] = 1;
    }

    let visited = new Array(N).fill(0).map(() => new Array(M).fill(false));

    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            if (checkArr[i][j] === 2 && !visited[i][j]) {
                bfs(i, j, visited, checkArr);
            }
        }
    }

    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            if (checkArr[i][j] === 0) {
                cnt += 1;
            }
        }
    }

    ans = Math.max(ans, cnt);
}

console.log(ans);