[JS][백준]14502_연구소

문제 번호

14502번: 연구소

 

 

알고리즘 분류

그래프 이론, 그래프 탐색, 브루트포스, 너비 우선 탐색

 

문제 풀이

 브루트포스와 그래프 탐색을 모두 이용해야 하는 문제이다.

 

우선 브루트포스 알고리즘을 사용하여 주어지는 지도에 벽3개를 세울 수 있는 경우를 모두 다 조사해야한다.

function solution(y, x) {
  if (cnt === 0) {
    return count();
  }

  for (let i = y; i <= N; i++) {
    for (let j = x; j <= M; j++) {
      if (map[i][j] === 0) {
        cnt--;
        map[i][j] = 1
        solution(y, x);
        cnt++;
        map[i][j] = 0;
      }
    }
  }
}

 

그 다음 주어진 연구소 배열을 map2라는 배열에 옮겨담는다. map2 배열을 탐색하면서 바이러스('2')가 발견될때마다 BFS를 실행한다. 그렇게 (N, M)까지 모든 탐색과 BFS를 마치면 MAP2 를 다시 탐색하면서 안전지역의 갯수를 새어준다.

function count() {
  // for(let i=1; i<=N; i++){
  //   for(let j=1; j<=M; j++){
  //     map2[i][j] = map[i][j];
  //   }
  // }
  map2 = map.map(v => v.slice());

  let visited = new Array(10);
  for (let i = 0; i < 10; i++) {
    visited[i] = new Array(10).fill(false);
  }

  for (let i = 1; i <= N; i++) {
    for (let j = 1; j <= M; j++) {
      if (map2[i][j] === 2) {
        BFS(i, j, visited);
      }
    }
  }

  let safe = 0;
  for (let i = 0; i < 10; i++) {
    for (let j = 0; j < 10; j++) {
      if (map2[i][j] === 0)
        safe++;
    }
  }

  if (safe > max) {
    max = safe;
  }
}

 

BFS

function BFS(y, x, visited) {
  let queue = [];
  queue.push([y, x]);
  visited[y][x] = true;

  while (queue.length > 0) {
    let xy = queue.shift();
    let cy = xy[0];
    let cx = xy[1];

    for (let next = 0; next < 4; next++) {
      let nextY = cy + dxy[next][0];
      let nextX = cx + dxy[next][1];

      if (!visited[nextY][nextX] && map2[nextY][nextX] === 0) {
        queue.push([nextY, nextX]);
        visited[nextY][nextX] = true;
        map2[nextY][nextX] = 2;
      }
    }
  }
}

 

전체코드

//let tt = 0;

const fs = require('fs');
const input = fs.readFileSync('연구소/input.txt').toString().split('\n');
const NM = input.shift().split(' ');
const N = Number(NM.shift());
const M = Number(NM.shift());
let dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]];
let cnt = 3;
let max = 0;

let map = new Array(10);
for (let i = 0; i < 10; i++) {
  map[i] = new Array(10);
}

let map2 = new Array(10);
for (let i = 0; i < 10; i++) {
  map2[i] = new Array(10);
}

for (let i = 1; i <= N; i++) {
  let temp = input.shift().split(' ');
  for (let j = 1; j <= M; j++) {
    map[i][j] = Number(temp[j - 1]);
  }
}

function BFS(y, x, visited) {
  let queue = [];
  queue.push([y, x]);
  visited[y][x] = true;

  while (queue.length > 0) {
    let xy = queue.shift();
    let cy = xy[0];
    let cx = xy[1];

    for (let next = 0; next < 4; next++) {
      let nextY = cy + dxy[next][0];
      let nextX = cx + dxy[next][1];

      if (!visited[nextY][nextX] && map2[nextY][nextX] === 0) {
        queue.push([nextY, nextX]);
        visited[nextY][nextX] = true;
        map2[nextY][nextX] = 2;
      }
    }
  }
}

function count() {
  // for(let i=1; i<=N; i++){
  //   for(let j=1; j<=M; j++){
  //     map2[i][j] = map[i][j];
  //   }
  // }
  map2 = map.map(v => v.slice());

  let visited = new Array(10);
  for (let i = 0; i < 10; i++) {
    visited[i] = new Array(10).fill(false);
  }

  for (let i = 1; i <= N; i++) {
    for (let j = 1; j <= M; j++) {
      if (map2[i][j] === 2) {
        BFS(i, j, visited);
      }
    }
  }

  let safe = 0;
  for (let i = 0; i < 10; i++) {
    for (let j = 0; j < 10; j++) {
      if (map2[i][j] === 0)
        safe++;
    }
  }

  if (safe > max) {
    max = safe;
  }
}

function solution(y, x) {
  if (cnt === 0) {
    return count();
  }

  for (let i = y; i <= N; i++) {
    for (let j = x; j <= M; j++) {
      if (map[i][j] === 0) {
        cnt--;
        map[i][j] = 1
        solution(y, x);
        cnt++;
        map[i][j] = 0;
      }
    }
  }
}

solution(1, 1)
console.log(max);

특이사항

문제가 어렵진 않았으나 오타를 못봐서 지ㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣ이니ㅣㅣㅣㅣㅣㅣㅣㅣㅣ짜 오래걸렸다.

항상 집중해서 문제를 풀고 변수명을 쉽고, 알아보기 쉽게, 가독성 좋게 쓰자..........................................

분명 꼼꼼하게 50번도 넘게 봤는데 안보였다...

 

2차원 배열은 let arr2 = arr1.map(x => x.slice()) 와 같은 형태로 복사 할 수 있다.