[백준] 14502번 - 연구소 (nodejs /조합, BFS)

문제

14502번: 연구소

 

💻 풀이

벽을 세울 위치는 조합으로 구했다. (재귀)

그렇게 구한 벽의 조합들을 다 세워보고 BFS로 바이러스를 퍼트린다. (BFS, 브루트포스)

 

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

 

처음에 이런 데이터가 주어지면 split으로 쪼개며 map으로 넣는 과정에서 빈칸(0)과 바이러스(2)가 들어있는 위치도 따로 배열에 저장해준다. 각각 나중에 벽을 세울 빈 공간을 탐색할 때와, 바이러스를  퍼트릴 시작점을 찾기 위함이다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, M] = input[0].trim().split(' ').map(Number);
const map = [];
const viruses = [];
const empty = [];

const dx = [0, 0, -1, 1];
const dy = [1, -1, 0, 0];

for (let y = 1; y <= N; y++) {
  const line = input[y]
    .trim()
    .split(' ')
    .map((el, x) => {
      const cell = Number(el);
      if (cell === 2) {
        viruses.push([x, y - 1]);
      } else if (cell === 0) {
        empty.push([x, y - 1]);
      }
      return cell;
    });
  map.push(line);
}

 

 

벽 조합 구하기

count는 여태 몇 개의 조합을 구했는지 세고, 재귀를 종료하기 위한 변수이다.

selected는 현재의 조합을 저장하기 위한 배열이다. count가 0이 되면 현재의 조합인 selected를 result 배열에 저장하게 된다.

재귀를 할 때 start가 현재 값에 +1 되어서 호출되기 때문에 3중 for문을 쓸 필요가 없고, for문을 돌릴 때 세 값이 모두 같은 경우를 방지할 수 있다. 그리고 재귀로 getCombination을 호출하는 다음 줄에 selected.pop()을 배치해서

예를 들면 [[x1, y1], [x2, y2], [x3, y3]] 이렇게 조합을 구했다면 [[x1, y1], [x2, y2]]로 배열을 되돌려 다음 조합인 [[x1, y1], [x2, y2], [x4, y4]]를 구할 수 있도록 배열을 초기화해준다.

function getCombination(count, arr, start = 0, selected = [], result = []) {
  if (count === 0) {
    result.push([...selected]);
    return;
  }

  for (let i = start; i < arr.length; i++) {
    selected.push(arr[i]);
    getCombination(count - 1, arr, i + 1, selected, result);
    selected.pop();
  }

  return result;
}

 

bfs 부분은 전체 코드 부분을 참조하고

 

main 함수

빈 칸에 세울 수 있는 벽들의 조합을 구하고, walls를 돌며 map의 복사본에 벽을 세워본 다음, viruses의 시작점을 돌며 bfs로 바이러스를 퍼트린다.

 

이 때 map을 복사하는 방법에 주의하자. for문으로 각 줄을 돌며 slice로 복사하거나, spread로 각 줄의 내용물을 복사해야 한다. 복사할 때 slice와 spread 문법 두 가지 방법을 모두 써봤는데 모두 결과가 이상하게 나와서 원인을 살펴보니 2차원 배열이라서 그랬다. 깊은 복사가 되는 것은 배열의 내용물이 원시값일 때에만 해당되고, 내용물이 배열인 경우에는 그 배열의 주소값을 복사해서 얕은 복사가 되버린다.

나는 얕은 복사를 해버린 셈이 되어 map이 오염되어서 결과가 이상하게 나온 거였다.그래서 각 줄을 돌며 깊은 복사하는 방법이 귀찮아 JSON 문자열 함수로 map을 복사했다.

 

각 벽을 세운 경우를 시뮬레이션 해봐서 새로운 maxCount라면 갱신해주고, 최종적으로 출력한다.

function solution() {
  const walls = getCombination(3, empty);
  let maxCount = 0;

  walls.forEach((locations) => {
    let count = 0;
    const newMap = JSON.parse(JSON.stringify(map));

    for (let i = 0; i < 3; i++) {
      const [x, y] = locations[i];
      newMap[y][x] = 1;
    }

    viruses.forEach((viruse) => {
      bfs(viruse, newMap);
    });

    for (let i = 0; i < N; i++) {
      for (let j = 0; j < M; j++) {
        if (newMap[i][j] === 0) {
          count += 1;
        }
      }
    }

    maxCount = Math.max(maxCount, count);
  });

  console.log(maxCount);
}

 

 

전체 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, M] = input[0].trim().split(' ').map(Number);
const map = [];
const viruses = [];
const empty = [];

const dx = [0, 0, -1, 1];
const dy = [1, -1, 0, 0];

for (let y = 1; y <= N; y++) {
  const line = input[y]
    .trim()
    .split(' ')
    .map((el, x) => {
      const cell = Number(el);
      if (cell === 2) {
        viruses.push([x, y - 1]);
      } else if (cell === 0) {
        empty.push([x, y - 1]);
      }
      return cell;
    });
  map.push(line);
}

function getCombination(count, arr, start = 0, selected = [], result = []) {
  if (count === 0) {
    result.push([...selected]);
    return;
  }

  for (let i = start; i < arr.length; i++) {
    selected.push(arr[i]);
    getCombination(count - 1, arr, i + 1, selected, result);
    selected.pop();
  }

  return result;
}

function bfs(start, map) {
  const queue = [start];
  while (queue.length > 0) {
    const [x, y] = queue.shift();
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];

      if (nx >= 0 && nx < M && ny >= 0 && ny < N && map[ny][nx] === 0) {
        map[ny][nx] = 2;
        queue.push([nx, ny]);
      }
    }
  }
}

function solution() {
  const walls = getCombination(3, empty);
  let maxCount = 0;

  walls.forEach((locations) => {
    let count = 0;
    const newMap = JSON.parse(JSON.stringify(map));

    for (let i = 0; i < 3; i++) {
      const [x, y] = locations[i];
      newMap[y][x] = 1;
    }

    viruses.forEach((viruse) => {
      bfs(viruse, newMap);
    });

    for (let i = 0; i < N; i++) {
      for (let j = 0; j < M; j++) {
        if (newMap[i][j] === 0) {
          count += 1;
        }
      }
    }

    maxCount = Math.max(maxCount, count);
  });

  console.log(maxCount);
}

solution();