백준 26085 효구와 호규

문제

N * M 2차원 배열에서 카드를 탐색하면서 없애거나 옮겨서 모든 카드를 없애는 방법을 찾는 문제이다.

처음에는 무조건 그래프 탐색 문제일 거라 생각했는데, 조건이 너무 그대로 그래프 탐색을 적용하기 애매한 알고리즘이라 뭔가 해서 봤더니 애드혹이었다.. 스트렛으… 해당 문제에서 카드를 모두 없앨 수 있는 경우는 두 가지가 있는데 서로 필요충분조건이다.

• 1과 0이 각각 짝수여야 한다
  • 해당 조건은 무조건 두개씩 없애야 한다는 조건이 있기 때문에 애초에 0과 1이 홀수면 성립 자체가 불가능하다.
• 0과 1중에 없어지는게 하나라도 있어야 한다.
  • 인접해서 없어지는게 하나라도 있다면 몇번을 움직이든지 애들끼리 지지고볶고 해서 없어질텐데, 서로가 완벽하게 겹치는게 하나도 없다면 움직이지조차 못하기 때문에 불가능하다.

이러한 조건을 만족하기 위해, 처음에는 짝수인지 세고 두번째로는 그래프 탐색을 통해 알아보면 된다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
const [n, m] = inputs[0].split(" ").map(Number);
const cards = inputs.slice(1).map((c) => c.split(" ").map(Number));
 
let acc1 = 0;
let acc0 = 0;
for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    if (cards[i][j] === 1) {
      acc1++;
    } else acc0++;
  }
}
const pos1 = acc1 % 2 === 0 && acc0 % 2 === 0;
if (!pos1) {
  console.log(-1);
  process.exit(0);
}
 
let possible = false;
const dLoc = [
  [-1, 0],
  [0, 1],
  [0, -1],
  [1, 0],
];
 
for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    for (const [dr, dc] of dLoc) {
      const nr = i + dr;
      const nc = j + dc;
      if (nr >= 0 && nc >= 0 && nr < n && nc < m) {
        if (cards[i][j] === cards[nr][nc]) {
          console.log(1);
          process.exit(0);
        }
      }
    }
  }
}
 
console.log(-1);