[Javascript] 백준 1743: 음식물 피하기

문제
코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다.

이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다.

통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다.

선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자.

입력
첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.

좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다. 입력으로 주어지는 좌표는 중복되지 않는다.

출력
첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라.

정답코드

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

let answer = [];
const map = Array.from({ length: N }, () => Array(M).fill(0));
const visited = Array.from({ length: N }, () => Array(M).fill(false));
const dx = [0, 0, -1, 1];
const dy = [-1, 1, 0, 0];
input.forEach(([y, x]) => {
  map[y - 1][x - 1] = 1;
});

let result = 1;
const dfs = (y, x) => {
  visited[y][x] = true;

  for (let k = 0; k < 4; k++) {
    let ny = y + dy[k];
    let nx = x + dx[k];

    if (
      ny >= 0 &&
      ny < N &&
      nx >= 0 &&
      nx < M &&
      map[ny][nx] === 1 &&
      !visited[ny][nx]
    ) {
      result += 1;
      dfs(ny, nx);
    }
  }
};

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (map[i][j] === 1) {
      dfs(i, j);
      answer.push(result);
      result = 1;
    }
  }
}

console.log(Math.max(...answer));

문제풀이
이번 문제는 DFS에 알고 있으면 간단하게 풀 수 있었던 문제 같다.
주어진 크기에 map을 만들고 음식물이 떨어진 좌표에 1에 값을 넣어준다.
map과 똑같은 크기로 방문 표시를 할 visited 배열도 만든다.
그리고 이제 전체 map을 순회하는데 1일 때 방문하므로 처음 음식물이 떨어진 좌표에 방문했다면
처음 발견 값인 result를 1로 설정해 주고 4방향(좌, 우, 위, 아래)에 인접한 음식물이 있으면 1을 더해주면서 탐색하고 탐색한 곳은 방문 처리를 하면서 크기들을 기록해 나간 뒤 최댓값을 출력해 주면 된다.

주의할 점은 입력 설명에 "좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다."라고 적혀 있는데 주어지는 좌표는 x, y 순서가 아닌 y, x로 반대 순서로 들어온다는 것을 고려해야 한다.