[ JavaScript (Node.js) ] 백준 실버1 1743번 음식물 피하기

음식물 피하기 #1743

음식물 피하기 성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

 

2 초

128 MB

19737

9366

7420

47.494%

문제

코레스코 콘도미니엄 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가 된다. (인접한 것은 붙어서 크게 된다고 나와 있음. 대각선으로는 음식물 끼리 붙을수 없고 상하좌우로만 붙을수 있다.)

풀이

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
const [N, M, K] = input[0].split(" ").map((i) => parseInt(i));

const map = Array.from({ length: N }, () =>
  Array.from({ length: M }, () => false)
);
const visited = Array.from({ length: N }, () => Array(M).fill(false));

for (let i = 1; i <= K; i++) {
  const [x, y] = input[i].split(" ").map(Number);
  map[x - 1][y - 1] = true;
}

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

let max = 0;
let count = 0;

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (!visited[i][j] && map[i][j]) {
      count = 0;
      dfs(i, j);
      max = Math.max(max, count);
    }
  }
}
console.log(max);

function dfs(x, y) {
  count++;
  visited[x][y] = true;
  for (let i = 0; i < 4; i++) {
    const nextX = x + dx[i];
    const nextY = y + dy[i];

    if (
      nextX >= 0 &&
      nextY >= 0 &&
      nextX < N &&
      nextY < M &&
      map[nextX][nextY] &&
      !visited[nextX][nextY]
    ) {
      dfs(nextX, nextY);
    }
  }
  return count;
}

• 깊이 우선 탐색(DFS)로 해결했다. 
• 음식물이 있으면 true, 없으면 false 값을 가지고 있는 map 배열
• 방문 배열인 visited 배열을 초기화해준다. 
• N*M만큼 for문을 돌아서, 음식물이 있으면서, 아직 방문하지 않은 배열이면 dfs를 호출한다. 
  • 호출하기 전에 기존 계산 때문에 count값이 바뀌었을 수 있으므로, 0으로 초기화 하고 호출한다. 
  • dfs에 들어오면 일단 count를 증가시킨다. (음식물 찾음 +1)
  • 방문배열을 true로 바꾼다.
  • 보통 BFS에서 썼던 상하좌우 탐색을 해서 그곳에 음식물이 있고, 방문하지 않았다면 dfs를 재귀호출한다.
  • DFS를 다 돌고 돌아오면 찾은 음식물만큼 count값이 변경되었을 것이고, 이 값을 max와 비교해 더 크면 max에 count를 넣는다.  
• max를 출력한다. 

 

트러블 슈팅

처음에는 BFS로 풀고자 했다.

예제 문제는 통과했고, 제출하면 채점중 8%에서 진행되지 않고, 시간초과가 뜨며 실패했다.

구글링을 해보니, 다른 언어(Python, Java...)는 BFS로 해결한 풀이가 있었다.

하지만 JavaScript로 푼 것은 찾지 못했다.

아마, JavaScript에서만 시간초과가 뜰 수도 있다.(확실x) 

헤매다가 결국엔 위처럼 DFS로 해결했다. 

// 생략 (위와 같음)

let max = 0;

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (!visited[i][j] && map[i][j]) {
      const cnt = bfs(i, j);
      max = Math.max(max, cnt);
    }
  }
}
console.log(max);

function bfs(x, y) {
  const queue = [[x, y]];
  let count = 0;
  while (queue.length > 0) {
    const [curX, curY] = queue.shift();
    count++;
    map[curX][curY] = false;

    for (let i = 0; i < 4; i++) {
      const nextX = curX + dx[i];
      const nextY = curY + dy[i];

      if (
        nextX >= 0 &&
        nextY >= 0 &&
        nextX < N &&
        nextY < M &&
        map[nextX][nextY] &&
        !visited[nextX][nextY]
      ) {
        queue.push([nextX, nextY]);
      }
    }
  }
  return count;
}