[백준 | node.js] 14502번: 연구소 BFS, DFS, 백트래킹 풀이

백준 14502번 연구소 문제 링크

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

---

문제 정리

- 안전 영역 크기의 최댓값을 구하는 문제

- 0: 빈 칸, 1: 벽, 2: 바이러스가 있는 곳

- 바이러스는 벽 부분을 제외하고 상하좌우 방향으로 바이러스를 전파한다.

문제 출력

- 안전 영역 크기의 최댓값을 구하여라.

문제 접근

0. 문제 유형 파악하기

바이러스가 벽 부분을 제외하고 전파하는데, 안전 영역이 최댓값이 되려면 바이러스 전파가 최소화되어야 하므로걸리는 BFS 로 풀이한다. (3 ≤ N, M ≤ 8)의 범위가 주어졌기에 시간복잡도는 크게 신경쓰지 않았다. (+ 벽을 세우는 부분은 모든 가능성을 확인해야 하기 때문에 DFS로 풀이한다.)

 

1. 초기 설정

- 상하좌우 방향 벡터를 설정한다.

- result: 안전 영역의 최대 크기를 저장한다.

- copyArr : 시뮬레이션을 위해서 지도 배열을 복사한다.

- queue : 바이러스의 위치를 저장하는 곳

 

2. 바이러스 위치 찾아서 큐에 담기

-  copyArr를 탐색해서 바이러스의 위치를 queue에 저장한다.

 

3. BFS 로 바이러스 전파하기

- queue에서 꺼낸 바이러스의 위치 4방향을 탐색한다.

- 유효성 검사를 마치고, 전파된 바이러스의 새로운 위치를 큐에 push한다.

 

4. 전파 후 안전 영역 확인하기

- 이중for문을 사용하여 0인 부분을 센다.

 

5. DFS를 사용하여 벽세우기

- 이중for문을 사용하여 0인 부분에 대해 벽을 세운다.

- 3번째 벽에 대해서 매개변수로 받은 arr에 대해서 시뮬레이션을 위해 복사한다.

- 최대 안전 영역을 반환한다.

---

최종 코드

function solution(n, m, arr) {
  let result = 0;
  let dx = [-1, 1, 0, 0];
  let dy = [0, 0, -1, 1];
  
  // 바이러스 찾기 bfs 탐색
  function virus(copyArr) {
    let queue = []; // 바이러스의 위치 정보
    // 바이러스 위치 찾아서 큐에 담기
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < m; j++) {
        if (copyArr[i][j] === 2) {
          queue.push([i, j]);
        }
      }
    }
    // 바이러스 전파
    while (queue.length > 0) {
      let [x, y] = queue.shift();
      for (let i = 0; i < 4; i++) {
        let nx = x + dx[i];
        let ny = y + dy[i];

        // 유효성 검사
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (copyArr[nx][ny] !== 0) continue;
        copyArr[nx][ny] = 2; // 바이러스 전파됨
        queue.push([nx, ny]);
      }
    }
    let safeCount = 0;
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < m; j++) {
        if (copyArr[i][j] === 0) {
          safeCount++;
        }
      }
    }

    return safeCount;
  }

  // dfs를 활용한 벽세우기 => 모든 경우를 따져야하기 때문에 dfs
  function wall(count) {
    if (count === 3) {
      const copyMap = arr.map((row) => [...row]); // 시뮬레이션을 돌려야하기 때문에 배열 복사
      const safe = virus(copyMap);
      result = Math.max(result, safe);
      return result;
    }
    // 벽 세우는 과정
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < m; j++) {
        if (arr[i][j] === 0) {
          arr[i][j] = 1;
          wall(count + 1);
          arr[i][j] = 0;
        }
      }
    }
  }
  wall(0);
  return result;
}

+ 놓친 부분

두가지 알고리즘의 결합

바이러스 전파와 벽세우기를 어떻게 결합해야 할지 어려웠다. 하지만 역할을 분리하고 나니 이해가 잘 되었다.

1) 가능한 모든 벽 조합을 시도 한다. → DFS

2) 각 벽 조합에서 바이러스 전파 시뮬레이션을 돌린다. → BFS

 

백트래킹 이해

딱히 백트래킹 문제를 풀어본 경험이 없었던 것 같다.

벽을 세운다. → 다음 벽을 세우도록 한다. → 벽을 제거한다.

 

백트래킹 문제도 많이 풀도록 해야지..