[백준1012_자바스크립트(javascript)] - 유기농 배추

🔴 문제

유기농 배추

🟡 Sol

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

const maps = [];
let map = [];

// 테스트 케이스 분리 / 맵 생성
for (const tc of testCase) {
  if (tc.length === 3) {
    const [m, n, k] = tc;
    if (map.length !== 0) maps.push(map);
    map = Array.from({ length: n }, () => Array.from({ length: m }, () => 0));
  } else {
    const [y, x] = tc;
    map[x][y] = 1;
  }
}
maps.push(map);

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

// bfs 구현
function bfs(x, y, m, n, map) {
  const q = [];
  q.push([x, y]);

  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 >= m || ny >= n) continue;

      if (map[nx][ny] === 1) {
        map[nx][ny] = 0;
        q.push([nx, ny]);
      }
    }
  }
}

for (const map of maps) {
  const [m, n] = [map.length, map[0].length];
  let cnt = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (map[i][j] === 1) {
        bfs(i, j, m, n, map);
        cnt++;
      }
    }
  }
  console.log(cnt);
}

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [t, ...inputs] = fs.readFileSync(path).toString().trim().split('\r\n');
const testCase = inputs.map((it) => it.split(' ').map((it) => Number(it)));

const maps = [];
let map = [];

// 테스트 케이스 분리 / 맵 생성
// 입력진짜 쓰레기같음
for (const tc of testCase) {
  if (tc.length === 3) {
    const [m, n, k] = tc;
    if (map.length !== 0) maps.push(map);
    map = Array.from({ length: n }, () => Array.from({ length: m }, () => 0));
  } else {
    const [y, x] = tc;
    map[x][y] = 1;
  }
}
maps.push(map);

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

  if (map[x][y] === 1) {
    map[x][y] = 0;

    dfs(x + 1, y, m, n, map);
    dfs(x - 1, y, m, n, map);
    dfs(x, y + 1, m, n, map);
    dfs(x, y - 1, m, n, map);

    return true;
  }

  return false;
}

for (const map of maps) {
  const [m, n] = [map.length, map[0].length];
  let cnt = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (dfs(i, j, m, n, map)) cnt++;
    }
  }
  console.log(cnt);
}

🟢 풀이

dfs/bfs 유형문제다. 테스트 케이스가 여러개라서 입력이 지저분함 ...
문제 자체는 쉬우니 차근차근 보자면!
테스트케이스가 여러개니 테스트케이스 별로 맵을 생성해준다.
생성된 map들은 maps 배열에 담아주고 이 배열을 순회하면서 bfs를 수행해준다.
즉 maps를 순회하면서 중첩 for문으로 x, y좌표를 넘겨주며 bfs를 순회해주는 것이다!
map별로 가로, 세로, 순회좌표, map 다 다르기 때문에 매개변수로 5개의 값을 넘겨주었다.
dfs도 동일하게 푿이해준다.

🔵 Ref