https://www.acmicpc.net/problem/14502
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크
www.acmicpc.net
작성한 코드
// 14502
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'Beakjoon/Gold/test.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');
const [n, m] = input.shift().split(' ').map(Number);
const board = input.map((i) => i.split(' ').map(Number));
let answer = 0;
const solution = () => {
const buildWalls = (count) => {
if(count === 3){
const tempArr = board.map(v => [...v]);
const safeAreaCount = countSafeArea(tempArr);
answer = Math.max(answer, safeAreaCount);
return;
}
for(let i=0;i<n;i++){
for(let j=0;j<m;j++){
if(board[i][j] === 0){
board[i][j] = 1;
buildWalls(count+1);
board[i][j] = 0;
}
}
}
}
const countSafeArea = (arr) => {
const spreadVirus = (x, y) => {
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
for(let i=0;i<4;i++){
const nx = x + dx[i];
const ny = y + dy[i];
if(nx >= 0 && nx < n && ny >=0 && ny <m) {
if(arr[nx][ny] === 0){
arr[nx][ny] = 2;
spreadVirus(nx, ny);
}
}
}
}
for(let i=0;i<n;i++){
for(let j=0;j<m;j++){
if(arr[i][j] === 2){
spreadVirus(i,j);
}
}
}
let safeAreaCount = 0;
for(let i=0;i<n;i++){
for(let j=0;j<m;j++){
if(arr[i][j] === 0) {
safeAreaCount++;
}
}
}
return safeAreaCount;
}
buildWalls(0);
console.log(answer);
}
solution();
📍 풀이
- 이것이 코딩테스트다 - 파이썬 서적 보면서 먼저 정리 -> 풀이
- 자바스크립트 버전으로 작성하며 참고한 블로그
https://velog.io/@ywc8851/%EB%B0%B1%EC%A4%80-14502-%EC%97%B0%EA%B5%AC%EC%86%8C-javascript

1. 벽 세우기
- dfs를 사용해서 벽의 개수가 3개가 되는 모든 경우의 수를 구함
- 벽의 개수가 3개가 되면, 안전 영역의 개수를 세주고, 해당 영역의 개수랑 기존의 답을 비교해서 더 큰 값을 답으로 설정
- 배열을 복사해서 보내는 이유는 안전영역을 구할 때 바이러스를 퍼트리면서 배열이 수정되기 때문에 원본 배열이 수정되지 않도록 복사 전달
const buildWalls = (count) => {
if(count === 3){
const tempArr = board.map(v => [...v]);
const safeAreaCount = countSafeArea(tempArr);
answer = Math.max(answer, safeAreaCount);
return;
}
for(let i=0;i<n;i++){
for(let j=0;j<m;j++){
if(board[i][j] === 0){
board[i][j] = 1;
buildWalls(count+1);
board[i][j] = 0;
}
}
}
}
2. 안전영역 세기
(1) 바이러스 퍼트리기
- 바이러스는 상하좌우로 퍼질 수 있음
- 그래서 현재 위치에서 상하좌우를 확인해서 해당 위치가 배열의 범위를 벗어나지 않고, 0이라서 감염이 가능한 곳이면
-> 2로 바꿔서 감염시키고 해당 위치에서 또다시 바이러스를 퍼트린다
const spreadVirus = (x, y) => {
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
for(let i=0;i<4;i++){
const nx = x + dx[i];
const ny = y + dy[i];
if(nx >= 0 && nx < n && ny >=0 && ny <m) {
if(arr[nx][ny] === 0){
arr[nx][ny] = 2;
spreadVirus(nx, ny);
}
}
}
}
(2) 안전영역의 개수 세기
- 바이러스가 존재하는 곳에서 바이러스 감염이 시작되는 것이기 때문에 2인 곳에서 바이러스 감염 시작
- 바이러스 감염이 전부 끝난 후에 안전영역인 0의 개수를 세서 반환함
const countSafeArea = (arr) => {
// spreadVirus 정의 ...
for(let i=0;i<n;i++){
for(let j=0;j<m;j++){
if(arr[i][j] === 2){
spreadVirus(i,j);
}
}
}
let safeAreaCount = 0;
for(let i=0;i<n;i++){
for(let j=0;j<m;j++){
if(arr[i][j] === 0) {
safeAreaCount++;
}
}
}
return safeAreaCount;
}
(3) 안전영역의 최댓값 구하기
- buildWalls에서 count === 3일때 구한 안전영역의 개수와 원래 안전 영역의 최댓값을 비교해서 다시 최댓값 설정
if(count === 3){
const tempArr = board.map(v => [...v]);
const safeAreaCount = countSafeArea(tempArr);
answer = Math.max(answer, safeAreaCount);
return;
}
📍 사담
- 참고로 적어놓은 블로그의 도움을 많이 받았다.
자바스크립트로 백준 문제를 푸는것은 진짜 번거로운데 쉽게 바꾸는 법을 적어놔주셔서 편하게 풀 수 있었다
또한 디버깅할때 파일 이름을 왔다갔다 바꾸는 것도 매우 번거로웠는데 저렇게 자동으로 적용되니까 너무 편했다!
- 함수의 인자를 잘못 전달해서 문제를 푸는데 어려움이 있었다. i,j로 전달해야 하는데, [i,j]로 전달해서 문제를 찾는데 한참 애먹었다
- dfs문제는 항상 접근법이 다양해서 풀 때 재밌기도 어렵기도 한 것 같다
- solution으로 묶지 않는게 더 깔끔할 것 같은데, 프로그래머스를 주로 풀어서 그런지 본능적으로 묶어서 작성했다.
'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/DFS] 백준 실버 1 : 14888 - 연산자 끼워넣기 (1) | 2023.08.18 |
|---|---|
| [JavaScript/BFS] 백준 골드 5 : 18405 - 경쟁적 전염 (0) | 2023.08.12 |
| [C++] - 백준(Baekjoon) : 4673번 셀프넘버 (0) | 2022.06.22 |
| [C] - 백준(Baekjoon) : 1546번 평균 (1) | 2022.06.16 |
| [C] - 백준(Baekjoon) : 2480번 주사위 3개 (0) | 2022.06.07 |