[백준/BOJ] 14502 연구소 (JavaScript)

🌱 문제

[백준/BOJ] 14502 연구소
지난 번 풀었던 14501 퇴사 문제에 이어 코딩테스트에 나왔던 문제랑 거의 비슷한 문제 2!!
코테에선 시간이 모자라 못 풀었지만 다시 풀어보려 한돠
고럼 스땄뜨

☘️ 풀이

흐름은 이러하다..!

1. 우선 벽을 세울 수 있는 좌표(0)들 중, 벽을 세울 좌표 3개의 조합을 만든다
   • 처음에 파이썬으로 풀 때 좌표 3개 조합이 아니라 벽을 세울 수 있는 모든 경우의 수를 고려해 for문을 돌렸는데 시간 초과가 났다 (흑흑)
2. 벽이 3개가 세워졌으면, 바이러스 좌표(2)부터 바이러스가 퍼질 수 있는 곳(0)을 2로 오염시킨다!
3. 바이러스가 다 퍼졌으면 남은 0의 개수를 세어 가장 큰 값을 출력한다!

---

그럼 먼저 조합 함수를 만든다! 파이썬에선 itertools.combination()으로 쉽게 했는데 알고리즘 언어를 js로 바꾼 뒤 이런 부분에서 모자람을 느꼈다ㅠㅠ

function getCombination(arr, r) {
  const result = [];
  const combine = (start, combo) => {
    if (combo.length === r) {
      result.push(combo);
      return; // 조합 완성된 후엔 result에 저장하고 상위 호출로 돌아감
    }
    for (let i = start; i < arr.length; i++) {
      // 다음 요소 추가, 더 이상 다음 요소 없으면 상위 호출로 돌아가고 다음 i 실행
      combine(i + 1, [...combo, arr[i]]); 
    }
  };
  combine(0, []);
  return result;
}

다음은 bfs로 바이러스를 전파시키고, 0의 개수를 세는 함수를 만든다

function countSafeZone(lab) {
  let cnt = 0;
  let queue = [];
  
  // 바이러스 좌표를 전부 queue에 넣어둠
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (lab[i][j] == 2) queue.push([i, j]);
    }
  }

  // queue를 돌며 바이러스 전파
  while (queue.length) {
    const [i, j] = queue.shift();
    let [ni, nj] = [0, 0];

    for (let d = 0; d < 4; d++) {
      ni = i + di[d];
      nj = j + dj[d];

      if (0 <= ni && ni < N && 0 <= nj && nj < M && lab[ni][nj] === 0) {
        lab[ni][nj] = 2;
        queue.push([ni, nj]);
      }
    }
  }
  
  // 바이러스 전파 후 안전지대(0) 개수 확인
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (lab[i][j] === 0) cnt += 1;
    }
  }

  // 전역에 선언해둔, 답으로 출력할 변수 safe_cnt에 cnt의 최댓값 저장
  safe_cnt = Math.max(safe_cnt, cnt);  
}

이로써 완성된 최종본 코드 !

const di = [-1, 0, 1, 0]; // 상우하좌
const dj = [0, 1, 0, -1];

function getCombination(arr, r) {
  const result = [];
  const combine = (start, combo) => {
    if (combo.length === r) {
      result.push(combo);
      return;
    }
    for (let i = start; i < arr.length; i++) {
      combine(i + 1, [...combo, arr[i]]);
    }
  };
  combine(0, []);
  return result;
}

function countSafeZone(lab) {
  let cnt = 0;
  let queue = [];

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (lab[i][j] == 2) queue.push([i, j]);
    }
  }

  while (queue.length) {
    const [i, j] = queue.shift();
    let [ni, nj] = [0, 0];

    for (let d = 0; d < 4; d++) {
      ni = i + di[d];
      nj = j + dj[d];

      if (0 <= ni && ni < N && 0 <= nj && nj < M && lab[ni][nj] === 0) {
        lab[ni][nj] = 2;
        queue.push([ni, nj]);
      }
    }
  }

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

  safe_cnt = Math.max(safe_cnt, cnt);
}

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
const [N, M] = input.shift().split(" ").map(Number);
const lab = input.map((i) => i.split(" ").map(Number));
let walls = [];
let safe_cnt = 0;

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (lab[i][j] === 0) walls.push([i, j]);
  }
}

// 벽 3개를 세우는 조합 구하기
const walls_comb = getCombination(walls, 3);

// 조합에 따라 벽 세우기
for (let i = 0; i < walls_comb.length; i++) {
  let new_lab = lab.map((x) => [...x]);
  for (const [x, y] of walls_comb[i]) {
    new_lab[x][y] = 1;
  }
	
  countSafeZone(new_lab);
}

console.log(safe_cnt);

• 이때 주의할 점은, 벽을 세우고 바이러스를 전파시키는 배열을 원본배열과 독립적으로 만들어서 관리해야 한다는 점 !
• 그래서 new_lab = lab.map((x) => [...x])에 벽을 세우고, countSafeZone에 넘겨주었다 !
  
  

🍀 결과

짠짠짠 ~.~

🐾 소소한 수확

let new_lab = lab.map(x => [...x]);

• lab의 얕은 복사이지만, lab의 내부 배열엔 원시값(Number) 만 포함되어 있기 때문에, new_lab은 lab의 내부 배열과 참조를 공유하지 않고 새로운 요소 배열 참조를 생성한다!
• 즉, new_lab 내부 배열의 요소를 재할당해도 lab에는 아무런 영향을 미치지 않으므로 깊은 복사처럼 작동할 수 있는 것 !
  
  
• 그럼 lab의 내부 배열에 중첩 배열 요소가 포함되어 있다묜?
  (ex. lab : [[0, 0], [0, [1, 2]])
  • lab[0]과 lab[1][0]은 위 설명처럼 깊은 복사처럼 작동함
  • lab[1][1]은 원시값이 아닌 중첩 배열이기 때문에 복사되면서 참조를 공유하므로 동일한 내부 배열을 가리킴
  • 따라서 new_lab[1][1]의 요소를 재할당하면 이는 lab에도 동일하게 적용된다!