[백준] 16988번, Baaaaaaaaaduk2 (Easy) (JavaScript)

Algorithm

문제 정보 : Baaaaaaaaaduk2 (Easy)

• 문제 분류 : 알고리즘 연습 중급 1/3, 이분탐색 (연습)
• 문제 출처 : 백준 골드 3, Baaaaaaaaaduk2 (Easy)

시작하며 ✅

문제 풀이까지는 했지만 시간 초과 때문에 오래걸린 문제였다.

접근 과정

처음엔 미리 적군의 바둑돌의 그룹들을 미리 찾아 구분한 후, DFS로 2개의 바둑돌의 위치를 정하여 미리 찾아둔 적 바둑돌 그룹들을 각각 BFS 탐색하는 방향으로 문제를 풀이했다. 그 결과 모든 예제를 통과할 수 있었지만 29% 정도에서 시간초과가 발생했다... C++로 동일한 로직을 구현한 분은 통과한 것 같은데 내 코드에서 문제가 조금 있었는지 JS 문제인지 모르겠다..ㅠㅠ

그래서 고민하다 BFS를 모든 적 바둑돌에 대하여 개별적으로 탐색하는 방향으로 구현하여 통과할 수 있었다.

중간에 예외 케이스가 하나 있어서 애 좀 먹었지만 해결하고 혹시 도움이 될까 싶어 질문 글에 올려두었다.
https://www.acmicpc.net/board/view/100257

풀이 과정 ✨

1. 적 바둑돌(2)의 위치를 모두 찾아두고 완전탐색으로 직접 나의 바둑돌(1)을 두었다.
2. 이후, BFS를 이용하여 모든 적 바둑돌(2)에 대하여 탐색을 하였고 조건을 만족하는 가장 큰 값을 출력했다.

코드 (시간초과 풀이)

// const readFileSyncAddress = '/dev/stdin';
const readFileSyncAddress = "text.txt";

let input = require("fs")
  .readFileSync(readFileSyncAddress)
  .toString()
  .split("\n");

const [N, M] = input[0].split(" ").map(Number);
const board = input.slice(1, 1 + N).map((line) => line.split(" ").map(Number));
const enemy = [];
let visited = [];
let answer = 0;

const dy = [0, 1, 0, -1];
const dx = [1, 0, -1, 0];

function solution() {
  const emptys = [];

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

  for (let i = 0; i < emptys.length; i++) {
    for (let j = i + 1; j < emptys.length; j++) {
      let acc = 0;

      const [fy, fx] = emptys[i];
      const [sy, sx] = emptys[j];

      board[fy][fx] = 1;
      board[sy][sx] = 1;

      // BFS 탐색
      // 모든 적 바둑돌 위치를 탐색
      visited = Array.from({ length: N }, () => new Array(M).fill(false));
      enemy.forEach((pos) => {
        const [y, x] = pos;

        acc += enemyBfs(y, x);
      });

      board[fy][fx] = 0;
      board[sy][sx] = 0;

      answer = Math.max(answer, acc);
    }
  }
}

function enemyBfs(y, x) {
  // 이미 탐색이 완료된 곳이면 리턴
  if (visited[y][x]) return 0;

  const q = [[y, x]];
  let [cy, cx] = [y, x];
  visited[cy][cx] = true;
  let cnt = 1;

  // 중요!, board[ny][nx] === 0 일 때, 리턴하면 bfs가 제대로 안 됨.
  let flag = false;

  while (q.length) {
    [cy, cx] = q.shift();

    for (let i = 0; i < 4; i++) {
      const ny = cy + dy[i];
      const nx = cx + dx[i];

      if (ny >= 0 && ny < N && nx >= 0 && nx < M) {
        if (board[ny][nx] === 0) {
          flag = true;
          continue;
        }

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

        if (board[ny][nx] === 2) {
          visited[ny][nx] = true;
          q.push([ny, nx]);

          cnt++;
        }
      }
    }
  }

  if (flag) return 0;
  else return cnt;
}

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

solution();
console.log(answer);

마치며 🚩

풀이 중 시간 초과 때문에 구글에 여러 코드를 찾아보았다. C++ 풀이는 정말 많았는데 js는 풀이글도 없고 나를 제외한 단 2분만이 이 문제를 해결했었다.. 코테는 C++로 준비하는게 맞는건가 싶지만.. 그래도 아직까지는 JS로 열심히 풀어봐야겠다.