[알고리즘/백준/5547] 일루미네이션(Nodejs, BFS)

문제

---

https://www.acmicpc.net/problem/5547

5547번: 일루미네이션

 

풀이

---

class Queue {
  constructor() {
    this.dat = [];
    this.head = 0;
    this.tail = 0;
  }

  push(item) {
    this.dat[this.tail++] = item;
  }

  pop() {
    this.head++;
  }

  front() {
    return this.dat[this.head];
  }

  rear() {
    return this.dat[this.tail - 1];
  }

  isEmpty() {
    return this.head === this.tail;
  }
}

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let [nums, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n");

const [W, H] = nums.split(" ").map(Number);
const board = arr.map((row) => row.split(" ").map(Number));


const dir = {
  even: [
    [-1, -1],
    [0, -1],
    [1, 0],
    [0, 1],
    [-1, 1],
    [-1, 0],
  ],
  odd: [
    [0, -1],
    [1, -1],
    [1, 0],
    [1, 1],
    [0, 1],
    [-1, 0],
  ],
};

// 1. 내부와 외부를 구분 
function checkOutdoor() {
  const ch = Array.from({ length: H }, () => Array(W).fill(0));

  for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
      if (board[i][j] === 1 || ch[i][j] === 1) continue;

      const q = new Queue();
      const outsideHomeArea = [];
      let isOutdoor = false;

      q.push([i, j]);
      ch[i][j] = 1;

      while (!q.isEmpty()) {
        const [x, y] = q.front();
        q.pop();
        outsideHomeArea.push([x, y]);

        // 아래로 이동하므로 x+1 해줘야 한다
        const key = (x + 1) % 2 === 0 ? "even" : "odd";

        for (let k = 0; k < 6; k++) {
          // 원래랑 반대로 이동
          const nx = x + dir[key][k][1];
          const ny = y + dir[key][k][0];

          if (nx < 0 || ny < 0 || nx >= H || ny >= W) {
            isOutdoor = true;
            continue;
          }

          if (board[nx][ny] === 1 || ch[nx][ny] === 1) continue;

          q.push([nx, ny]);
          ch[nx][ny] = 1;
        }
      }

      // 하나라도 바깥쪽과 맞닿아있는 경우 -1로 변경
      if (isOutdoor) {
        for (const [x, y] of outsideHomeArea) {
          board[x][y] = -1;
        }
      }
    }
  }
}

function getWallsToIlluminate() {
  const ch = Array.from({ length: H }, () => Array(W).fill(0));

  let answer = 0;

  for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
      if (board[i][j] !== 1 || ch[i][j] === 1) continue;

      // bfs
      const q = new Queue();
      q.push([i, j]);
      ch[i][j] = 1;

      while (!q.isEmpty()) {
        const [x, y] = q.front();
        const key = (x + 1) % 2 === 0 ? "even" : "odd";
        q.pop();

        for (let k = 0; k < 6; k++) {
          const nx = x + dir[key][k][1];
          const ny = y + dir[key][k][0];

          // 2. 배치도 바깥쪽 -> bfs 중단
          if (nx < 0 || ny < 0 || nx >= H || ny >= W) {
            answer += 1;
            continue;
          }

          // 3. 외부 -> bfs 중단
          if (board[nx][ny] === -1) {
            answer += 1;
            continue;
          }

          if (ch[nx][ny] === 0 && board[nx][ny] === 1) {
            ch[nx][ny] = 1;
            q.push([nx, ny]);
          }
        }
      }
    }
  }
  
  console.log(answer);
}

checkOutdoor();
getWallsToIlluminate();

 

해당 문제는 조명을 장식하는 벽면의 길이의 합을 구하는 문제이다. 

따라서 집을 bfs로 돌면서 집의 각 면에서 외부와 닿아있는 부분과 배치도를 벗어나는 부분을 센다.

즉, 회색 정육각형을 bfs로 돌면서 흰색 정육각형과 맞닿아 있는 경우, 그리고 아예 바깥쪽과 맞닿아 있는 경우 각각 1을 더한다.

 

단계는 아래와 같다. 

BFS: 홀수/짝수이냐에 따라 다르게 육각형의 6방향 확인
     1. checkOutdoor: 내부와 외부를 구분 -> 0이면서 bfs를 바깥이랑 맞닿은 경우를 외부로 본다.
     2. 1인 경우 돌면서 배치도 벗어나는 경우 +1
     3. 외부와 맞닿은 경우 +1 

 

헷갈렸던 부분이 bfs 문제를 풀 때 항상 x가 행으로, y가 열로 움직이도록 해서 풀어왔는데, 이 문제에서는 x의 이동이 일반 수학에서처럼 열을 기준으로 이동한다는 것이었다. 이에 대응하기 위해 dir로 6방향을 이동할 때 x, y를 바꿔주고, 행을 기준으로 짝수/홀수인 경우를 나눌 때 x값을 기준으로 해야했다. 아래의 코드 부분이다. 

while (!q.isEmpty()) {
        const [x, y] = q.front();
        q.pop();
        outsideHomeArea.push([x, y]);

        // 아래로 이동하므로 x+1 해줘야 한다
        const key = (x + 1) % 2 === 0 ? "even" : "odd";

        for (let k = 0; k < 6; k++) {
          // 원래랑 반대로 이동
          const nx = x + dir[key][k][1];
          const ny = y + dir[key][k][0];

          if (nx < 0 || ny < 0 || nx >= H || ny >= W) {
            isOutdoor = true;
            continue;
          }

          if (board[nx][ny] === 1 || ch[nx][ny] === 1) continue;

          q.push([nx, ny]);
          ch[nx][ny] = 1;
       }
}

 

짝수와 홀수에 따라 이동하는 방향이 달랐다는 점, 그리고 x, y 값의 기준이 통상적으로 풀었던 방식과는 달랐다는 점이 어려웠다. 

복습하면서 패턴을 찾고 이동하는 것에 대해 익숙해져야겠다. 

 

(2023/8/24 추가) 

시작점이 (1, 1)이기 때문에 짝홀수를 판단할 때 (x+1) % 2를 해야한다는 점에 유의해야 한다. 또한 처음에 0인 외부 영역을 지정할 때 시작점이 한 면이라도 map의 바깥과 맞닿아있는 경우만 nodes에 넣고 -1로 변경해주어야 한다. 이를 위해 isOutdoor이라는 변수를 이용해 nx가 map을 벗어난 경우 true로 변경하고, 이 때만 map을 변경해준다.