[백준1926_자바스크립트(javascript)] - 그림

🔴 문제

그림

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [nm, ...inputs] = fs.readFileSync(path).toString().trim().split('\n');

const [n, m] = nm.split(' ').map((it) => Number(it));
const maps = inputs.map((it) => it.split(' ').map((it) => Number(it)));

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

const q = [];
function bfs(x, y) {
  let size = 1;
  q.push([x, y]);
  maps[x][y] = 0;

  while (q.length) {
    const [x, y] = q.shift();

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

      if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

      if (maps[nx][ny] === 1) {
        size += 1;
        maps[nx][ny] = 0;
        q.push([nx, ny]);
      }
    }
  }
  return size;
}

const result = [0];
for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    if (maps[i][j] === 1) {
      result.push(bfs(i, j));
    }
  }
}

console.log(result.length - 1);
console.log(Math.max(...result));

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [nm, ...inputs] = fs.readFileSync(path).toString().trim().split('\n');

const [n, m] = nm.split(' ').map((it) => Number(it));
const maps = inputs.map((it) => it.split(' ').map((it) => Number(it)));

let size = 0;

function dfs(x, y) {
  if (x < 0 || y < 0 || x >= n || y >= m) return false;

  if (maps[x][y] === 1) {
    maps[x][y] = 0;
    size += 1;

    dfs(x + 1, y);
    dfs(x - 1, y);
    dfs(x, y + 1);
    dfs(x, y - 1);

    return true;
  }
  return false;
}

const result = [0];
for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    if (dfs(i, j)) {
      result.push(size);
      size = 0;
    }
  }
}

console.log(result.length - 1);
console.log(Math.max(...result));

🟢 풀이

bfs/dfs 기본문제유형
bfs일 경우 미방문 상태(map[i][j]===1)일 경우 bfs(i, j)를 수행한다. 한번 수행할 때 그림의 넓이를 리턴하도록 해 마지막에 가장 넓은 그림의 넓이를 출력할 수 있도록 한다.
dfs일 경우 항상 dfs(i, j)를 수행해 true 값을 리턴할 때만 넓이값을 배열에 추가해 마지막에 가장 넓은 그림의 넓이를 출력할 수 있도록 한다.

🔵 Ref