[백준 1743 - Node.js] 음식물 피하기

🔗 문제 링크

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

1743번: 음식물 피하기

✏️ 풀이

const [[N, M, K], ...input] = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n')
  .map(v => v.split(' ').map(Number));

const corridor = [...Array(N)].map(() => Array(M).fill(false));
input.forEach(([x, y]) => corridor[x - 1][y - 1] = true);
const offset = [[0, 1], [1, 0], [0, -1], [-1, 0]];

const dfs = (x, y, result = 0) => {
  let sum = result + 1;
  corridor[x][y] = false;
  offset.forEach(([dx, dy]) => {
    const nx = x + dx;
    const ny = y + dy;
    if (nx >= 0 && nx < N && ny >= 0 && ny < M && corridor[nx][ny]) {
      sum += dfs(nx, ny);
    }
  });
  return sum;
};

let largest = 0;

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (!corridor[i][j]) {
      continue;
    }
    largest = Math.max(largest, dfs(i, j));
  }
}

console.log(largest);

통로의 모든 칸을 순회하면서 DFS를 통해 현재 칸과 연결된 음식물의 개수를 모두 구하여 최댓값을 구하면 된다.

각 칸의 방문 여부는 최초에 음식물을 true, 빈 칸을 false로 초기화한 후에 음식물 칸을 방문할 때마다 false로 갱신하여 나타냈다.