[백준] 1743 음식물 피하기 Node.js (DFS 풀이)

문제

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

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

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

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

입력

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

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

출력

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

예제 입력 1

3 4 5
3 2
2 2
3 1
2 3
1 1

예제 출력 1

4

힌트

# . . .
. # # .
# # . .

위와 같이 음식물이 떨어져있고 제일큰 음식물의 크기는 4가 된다. (인접한 것은 붙어서 크게 된다고 나와 있음. 대각선으로는 음식물 끼리 붙을수 없고 상하좌우로만 붙을수 있다.)

---

문제풀이

💡 문제풀이 과정

• 입력값 두 번째 줄부터 [row, column]좌표가 주어지는데, 이 좌표를 이용하여 힌트와 같이 2차원 배열을 만들어 주는 작업을 진행한다. 나는 음식물이 떨어진 자리는 1, 나머지 자리는 0으로 채워주었다. 배열의 인덱스는 0부터 시작하므로 반복문을 통해 음식물이 떨어진 자리를 다음과 같이 표시 해 준다. graph[row - 1][col - 1] = 1;
• 탐색문 안에서 상,하,좌,우 인접한 네 곳도 음식물이 떨어진 곳이면 음식물 크기를 하나씩 증가시킨다.
• DFS - Stack과 재귀함수 두 가지로 풀이하였다. 제출 결과는 다음과 같다.

  	Stack	재귀함수
  메모리(KB)	12948	12584
  시간(ms)	200	188
  코드길이(B)	1026	875

✅ 답안 #1 : DFS - Stack 풀이

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = require('fs')
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n')
  .map((v) => v.split(' ').map(Number));
const [N, M, _] = input.shift();
const dir = [[0, 1], [0, -1], [-1, 0], [1, 0]]; // 인접한 상하좌우 x,y좌표

// 음식물 있는 곳 = 1, 없는 곳 = 0으로 채워진 graph 배열
const graph = Array.from(Array(N), () => Array(M).fill(0));
input.forEach(([r, c]) => graph[r - 1][c - 1] = 1);

const dfs = (r, c) => {
  let cnt = 1; // 현재 있는 곳도 카운팅에 포함하기 위해 초기값 1
  const stack = [[r, c]];
  while (stack.length) {
    const [cx, cy] = stack.pop();
    
    // 인접한 네방향 탐색을 위한 반복문
    for (let i = 0; i < 4; i++) {
      const x = cx + dir[i][0];
      const y = cy + dir[i][1];
      
      // 해당 위치 그래프 범위 안에 있고 음식물이 있는 곳(1)인 경우
      if (x >= 0 && x < N && y >= 0 && y < M && graph[x][y]) {
        graph[x][y] = 0; // 방문 처리
        cnt++; // 음식물 크기 증가
        stack.push([x, y]); // 해당 위치 스택에 담기
      }
    }
  }
  return cnt;
};

let result = 0; // DFS결과값 담을 변수(음식물 크기)
let max = 0; // 최대 음식물 크기를 담을 변수

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (graph[i][j]) {
      graph[i][j] = 0;
      result = dfs(i, j);
      if (result > max) max = result;
    }
  }
}
console.log(max);

✅ 답안 #2 : DFS - 재귀함수 풀이

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = require('fs')
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n')
  .map((v) => v.split(' ').map(Number));
const [N, M, _] = input.shift();
const dir = [[0, 1], [0, -1], [-1, 0], [1, 0]];
const graph = Array.from(Array(N), () => Array(M).fill(0));
input.forEach(([r, c]) => (graph[r - 1][c - 1] = 1));

let cnt = 1; // 현재 있는 곳도 카운팅에 포함하기 위해 초기값 1
const dfs = (r, c) => {
  for (let i = 0; i < 4; i++) {
    const x = r + dir[i][0];
    const y = c + dir[i][1];
    if (x >= 0 && x < N && y >= 0 && y < M && graph[x][y]) {
      graph[x][y] = 0;
      cnt++;
      dfs(x, y);
    }
  }
};

let max = 0;
for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (graph[i][j]) {
      graph[i][j] = 0;
      dfs(i, j);
      if (cnt > max) max = cnt;
      cnt = 1; // 초기화
    }
  }
}
console.log(max);