[백준 14502] 연구소
January 31, 2023
문제
https://www.acmicpc.net/problem/14502
고민
바이러스를 퍼뜨리는건 BFS 탐색으로 쉽게 가능할 것 같았는데, 퍼뜨리기 이전에 벽을 세 개를 설치해야 한다는 조건에서 어떻게 해결해야 할지가 많이 고민되었다.
벽을 설치할 최적의 위치를 어떻게 찾아야 하는지 고민이었는데 맵 전체 크기가 3x3 에서부터 8x8 까지로 무지하게 큰게 아니기 때문에 완전 탐색으로 모든 경우의 수를 계산해도 해결이 가능한 문제였다.
아이디어
- 입력 값을 가지고 전체 맵을 나타내는 2차원 배열을 만들고, 초기 바이러스 위치를 기억한다.
- 재귀적인 방식으로 모든 공간에 벽을 설치한다.
-
벽이 3개 설치되면 현재 맵의 정보를 깊은 복사하여 아래와 같은 로직을 수행하여 바이러스를 퍼뜨린다.
- 초기 바이러스의 좌표를 모두 큐에 넣는다.
-
큐가 비어있게 될 때까지, 꺼내면서 다음을 반복한다. (BFS 탐색)
- 현재 좌표의 상하좌우가 접근 가능한 공간이면 큐에 넣는다.
- 맵에 남은 안전구역의 갯수를 세고 기록한다.
소스코드
// 입력 정제
const fs = require("fs");
function getInput(caseID) {
const filePath = process.platform === "linux" ? "/dev/stdin" : `./${__dirname.split('\\').pop()}/i${caseID}.txt`;
const input = fs.readFileSync(filePath).toString().split("\n").map(item => item.trim());
input.pop();
const [n, m] = input.shift().split(" ").map(item => Number(item));
const map = [];
for (let i = 0; i < n; i++) {
map.push(input.shift().split(" ").map(item => Number(item)));
}
return [n, m, map];
}
// 문제
const [n, m, map] = getInput(3);
const originVirus = [];
let safetyCount = 0;
// 맵 배열을 깊은 복사하는 함수
function copyMap() {
const temp = Array.from({length: n}, () => Array.from({length: m}, () => undefined));
for (let y = 0; y < n; y++) {
for (let x = 0; x < m; x++) {
temp[y][x] = map[y][x];
}
}
return temp;
}
// 해당 좌표값이 유효한 범위인지 확인하는 함수
function isInBoundary(y, x) {
if (y < 0 || y >= n) return false;
if (x < 0 || x >= m) return false;
return true;
}
// 맵에서 안전구역의 갯수를 구하는 함수
function calculateSafetyZone(arr) {
let count = 0;
for (let y = 0; y < n; y++) {
for (let x = 0; x < m; x++) {
if (arr[y][x] !== 0) continue;
count++;
}
}
return count;
}
// 바이러스를 퍼뜨리는 함수
function spreadVirus(arr) {
let queue = [];
// 초기 바이러스 위치 모두 큐에 넣음.
originVirus.forEach(([y, x]) => queue.push([y, x]));
// 바이러스 퍼뜨리기
while (queue.length > 0) {
let [nowY, nowX] = queue.shift();
let dx = [1, 0, -1, 0];
let dy = [0, 1, 0, -1];
for (let i = 0; i < 4; i++) {
let nextY = nowY + dy[i];
let nextX = nowX + dx[i];
if (isInBoundary(nextY, nextX) && arr[nextY][nextX] === 0) {
arr[nextY][nextX] = 2;
queue.push([nextY, nextX]);
}
}
}
}
// 맵에 벽을 생성하는 함수. 3개까지 생성했으면 바이러스를 퍼뜨려본다.
function makeWall(arr, depth) {
// 벽을 3개 생성했으면 바이러스를 퍼뜨려본다.
if (depth === 3) {
const virusMap = copyMap(arr);
spreadVirus(virusMap);
safetyCount = Math.max(safetyCount, calculateSafetyZone(virusMap));
return;
}
// 모든 좌표에 벽을 생성해본다.
for (let y = 0; y < n; y++) {
for (let x = 0; x < m; x++) {
if (arr[y][x] !== 0) continue;
arr[y][x] = 1;
makeWall(arr, depth + 1);
arr[y][x] = 0;
}
}
}
function solution() {
// 초기 바이러스 위치 저장
for (let y = 0; y < n; y++) {
for (let x = 0; x < m; x++) {
if (map[y][x] !== 2) continue;
originVirus.push([y, x]);
}
}
makeWall(map, 0);
console.log(safetyCount);
}
// 실행
solution();