백준 15683 - 감시

문제

[https://www.acmicpc.net/problem/15683]

너무 길어서 안 퍼옴

접근법

문제를 요약해보면 각 cctv마다 경우의 수가 여러개 있고, 각 경우의 수마다 볼 수 있는 범위가 다르다고 생각하면 됨

1번의 경우 상/하/좌/우 총 4개의 경우의 수가 있고, 2번의 경우 상하/좌우 총 2개의 경우의 수가 있고, 5번의 경우 상하좌우 1개의 경우의 수가 있음

각 cctv의 경우의 수대로 지역을 조사한 후 (ex 1번이 경우의수 1234 중 1번을 가리키고 + 2번이 경우의수 12번 중2번을 가리키고 + ....)
그때마다 0의 몇개인지를 계산해서 그 최솟값을 찾으면 됨

그렇다면 백트래킹으로 첫번째 cctv가 조사하고, 그 다음 cctv가 조사하고...를 반복하면 되는데
cctv가 1번 2번 총 두개가 있다고 가정해보면, 1번이 상을 조사해서 배열에서 '#'로 바꿔주고, 이 배열을 재귀함수로 넘겨줘서 2번이 상하를 조사하면 모두 다 조사했기 때문에 함수가 리턴되면서, 2번째 cctv인 2번 cctv가 남은 경우의 수인 좌우를 조사할텐데,
여기서 우리가 바꾸는 값은 배열이라는 사실

만약에 그냥 변수를 넘겨준다면, return되어 다시 돌아온다면 바뀌기 전의 값을 가지고 있게 되지만
배열(그것도 이중배열)이기 때문에 return되어서 돌아온다고 해도 배열에 '#'로 바꿔준 건 그대로 남아있음

• 그래서 항상 다음 cctv로 넘어가기 전에, 배열을 deep copy 해야됨

const fs = require("fs");
let input = fs
  .readFileSync("./test.txt")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map((v) => Number(v)));

//각 cctv가 비출 수 있는 방향값의 경우의수를 모두 계산해줘야 함
//백트래킹에서는 방향값만 정해주면 됨
//그 방향값에 따라서 cctv 조사를 해서 최종 값들을 조사해서 거기서 최솟값을 return
const [n, m] = input.shift(); //i는 n까지,j는 m까지
//cctv를 찾기
const cctv = [];
for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    if (input[i][j] >= 1 && input[i][j] <= 5) {
      cctv.push([i, j]);
    }
  }
}
//각 cctv의 경우의 수 하나씩을 선택
const up = (x, y, map) => {
  const newMap = [];
  for (let i = 0; i < n; i++) {
    const arr = [];
    for (let j = 0; j < m; j++) {
      arr.push(map[i][j]);
    }
    newMap.push(arr);
  }
  for (let i = x; i >= 0; i--) {
    if (newMap[i][y] === 6) {
      break;
    }
    if (newMap[i][y] === 0) {
      newMap[i][y] = "#";
    }
  }
  return newMap;
};

const down = (x, y, map) => {
  const newMap = [];
  for (let i = 0; i < n; i++) {
    const arr = [];
    for (let j = 0; j < m; j++) {
      arr.push(map[i][j]);
    }
    newMap.push(arr);
  }
  for (let i = x; i < n; i++) {
    if (newMap[i][y] === 6) {
      break;
    }
    if (newMap[i][y] === 0) {
      newMap[i][y] = "#";
    }
  }
  return newMap;
};

const left = (x, y, map) => {
  const newMap = [];
  for (let i = 0; i < n; i++) {
    const arr = [];
    for (let j = 0; j < m; j++) {
      arr.push(map[i][j]);
    }
    newMap.push(arr);
  }
  for (let i = y; i >= 0; i--) {
    if (newMap[x][i] === 6) {
      break;
    }
    if (newMap[x][i] === 0) {
      newMap[x][i] = "#";
    }
  }
  return newMap;
};
const right = (x, y, map) => {
  const newMap = [];
  for (let i = 0; i < n; i++) {
    const arr = [];
    for (let j = 0; j < m; j++) {
      arr.push(map[i][j]);
    }
    newMap.push(arr);
  }
  for (let i = y; i < m; i++) {
    if (newMap[x][i] === 6) {
      break;
    }
    if (newMap[x][i] === 0) {
      newMap[x][i] = "#";
    }
  }
  return newMap;
};
let result = 64;

const bfs = (idx, map) => {
  console.log(map);
  if (idx >= cctv.length) {
    let sum = 0;
    map.forEach((i) => {
      i.forEach((v) => {
        if (v === 0) {
          sum += 1;
        }
      });
    });
    result = Math.min(sum, result);
    return;
  }
  let [x, y] = cctv[idx];
  const type = input[x][y];
  switch (type) {
    case 1:
      bfs(idx + 1, up(x, y, map));
      bfs(idx + 1, down(x, y, map));
      bfs(idx + 1, left(x, y, map));
      bfs(idx + 1, right(x, y, map));
      break;
    case 2:
      bfs(idx + 1, up(x, y, down(x, y, map)));
      bfs(idx + 1, right(x, y, left(x, y, map)));
      break;
    case 3:
      bfs(idx + 1, right(x, y, up(x, y, map)));
      bfs(idx + 1, right(x, y, down(x, y, map)));
      bfs(idx + 1, left(x, y, up(x, y, map)));
      bfs(idx + 1, left(x, y, down(x, y, map)));
      break;
    case 4:
      bfs(idx + 1, up(x, y, left(x, y, right(x, y, map))));
      bfs(idx + 1, down(x, y, left(x, y, right(x, y, map))));
      bfs(idx + 1, left(x, y, up(x, y, down(x, y, map))));
      bfs(idx + 1, right(x, y, up(x, y, down(x, y, map))));
      break;
    case 5:
      bfs(idx + 1, up(x, y, down(x, y, right(x, y, left(x, y, map)))));
      break;
  }
};
bfs(0, input);
console.log(result);

풀이

일단 상하좌우를 조사하는 걸 각각 함수로 쪼개서, 좌표와 배열을 받아서 이 배열을 deep copy한 후, 조건에 맞게 0을 '#'으로 바꿔준 후, copy본을 return해서 다음 cctv를 조사 할 때 사용함

• 이렇게 하면 2345번 처럼 상하, 상하우 같이 여러개를 처리해야 될때 up()의 리턴값으로 down() 의 리턴값으로 right() 하는 것처럼 여러개를 동시에 할 수 있음
  또한 기존의 처리하지 않은 배열은 그대로 남아있기 때문에('#'표시는 복사한 배열에 해놓음) return되어 돌아올 때도 변하지 않은 배열이 남아있음

배열을 다룰 때는 항상 내가 이 값 원본을 바꿔도 지장이 없는가 ?를 항상 생각해줘야 된다는 걸 깨닫는 문제...