백준 14502 연구소

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

문제 설명

문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

---

문제 풀이

input 처리

- 바이러스, 안전한 좌표를 각각 저장하는 배열에 input을 처리하면서 해당 좌표를 저장하도록 처리

search_safe_area 함수

- target_area(검사할 area), virus_list(바이러스 좌표 리스트) 를 가지고 바이러스트 퍼트린 후 안전한 구역의 갯수를 리턴하는 함수

while문

- input에서 구한 안전한 좌표를 저장한 배열에서 3개의 좌표를 선택하여 검사를 진행할 수 있도록 구현

const inputs = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [n, m] = inputs[0].split(" ").map(Number);
let area = [];

let virus_area = []; // 바이러스 좌표
let safe_area = []; // 안전한 좌표

for (let i = 1; i <= n; i++) {
  let rows = inputs[i].split(" ").map(Number);
  rows.forEach((row, index) => {
    if (row === 0) {
      safe_area.push([i - 1, index]);
    } else if (row === 2) {
      virus_area.push([i - 1, index]);
    }
  });
  area.push(rows);
}

const search_safe_area = (target_area, virus_list) => {
  // 매개변수로 받은 area에 바이러스를 퍼트린후 안전한 구역의 갯수 리턴
  let check_spot = [
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1],
  ];
  while (virus_list.length > 0) {
    let [virus_y, virus_x] = virus_list.shift();
    check_spot.forEach(([y, x]) => {
      let new_y = y + virus_y;
      let new_x = x + virus_x;
      if (
        new_y >= 0 &&
        new_y < n &&
        new_x >= 0 &&
        new_x < m &&
        target_area[new_y][new_x] === 0
      ) {
        target_area[new_y][new_x] = 2;
        virus_list.push([new_y, new_x]);
      }
    });
  }

  // 최종 안전한 구역 갯수 리턴
  return target_area.reduce((total, acc) => {
    return (total += acc.filter((a) => a === 0).length);
  }, 0);
};

// safe_area에서 3개의 벽을 설치할 수 있는 경우의 수 찾기
let first = 0;
let second = 1;
let third = 2;
let safe_area_max_size = 0; // 안전 영역의 최대 크기
while (true) {
  // 벽을 세운 area에서 안전한 구역이 얼마인지 검사
  let tmp = area.map((row) => [...row]);
  tmp[safe_area[first][0]][safe_area[first][1]] = 1;
  tmp[safe_area[second][0]][safe_area[second][1]] = 1;
  tmp[safe_area[third][0]][safe_area[third][1]] = 1;

  safe_area_max_size = Math.max(
    safe_area_max_size,
    search_safe_area(
      tmp,
      virus_area.map((va) => [...va])
    )
  );

  // 좌표 값을 수정
  if (third + 1 < safe_area.length) {
    third++;
  } else if (second + 1 < safe_area.length - 1) {
    second++;
    third = second + 1;
  } else if (first + 1 < safe_area.length - 2) {
    first++;
    second = first + 1;
    third = first + 2;
  } else {
    break;
  }
}

console.log(safe_area_max_size);

---

결론

search_safe_area에 인자로 배열의 복사본을 넘겨 원본에 영향을 안미치도록 하려고했는데 함수를 돌면서 원본이 바뀌어 동작이 꼬이는 문제가 생겼음

-> 2차원 배열을 단순히 let tmp = [...area] 형태로 복사를하여 1차원 값에 대해서는 깊은 복사가 이루어져 영향을 안미치지만 그 내부의 배열 값에 대해서는 깊은 복사가 이루어지지 않아 원본이 수정되는 문제가 생겼음

해결

배열 전체를 깊은 복사를 하기 위해서는 2차원 배열의 값을 전부 깊은 복사를 해야함

let tmp = area.map((row) => [...row])

 

+ 추가적으로 3개의 값을 선택하는 부분의 처리를 dfs를 이용해 처리를 하면 더 효율적으로 작성할 수 있을 것 같음..

2중 for 문을 돌면서 가능한 값을 1개씩 선택하면서 3개를 선택했을 때 안전한 구역을 검사하는 함수(bfs)를 호출하는 방식으로 로직을 구현하면 됨.

function dfs(count){
  if(count === 3){
    for(let i = 0; i < n; i++){
      for(let j = 0; j < m; j++){
        temp[i][j] = data[i][j];
      }
    }
    for(let i = 0; i < n; i++){
      for(let j = 0; j < m; j++){
        if(temp[i][j] === 2) virus(i, j);
      }
    }
    result = Math.max(result, getScore());
    return;
  }
  for(let i = 0; i < n; i++){
    for(let j = 0; j < m; j++){
      if(data[i][j] === 0){
        data[i][j] = 1;
        dfs(count + 1);
        data[i][j] = 0;
      }
    }
  }
}
dfs(0);