[JavaScript/DFS] 백준 골드 4 : 14502 - 연구소

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

14502번: 연구소

---

작성한 코드 

// 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으로 묶지 않는게 더 깔끔할 것 같은데, 프로그래머스를 주로 풀어서 그런지 본능적으로 묶어서 작성했다.