[Algorithm] 백준 1012번-유기농 배추

백준 1012번-유기농 배추

문제 파악

• 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.
• 배추 영역이 몇개인지 구하는 문제 !

백준 1012번-유기농 배추

풀이 과정

• 기존에 풀었던 bfs 문제 유형과 동일했다 - 영역 개수
• 풀이가 어려웠다기 보다는 x축 y축이 헷갈려서 계속 범위 오류가 발생했다. TypeError: Cannot read properties of undefined (reading '0') 즉, field[nx]가 undefined여서 field[nx][ny]를 읽을 수 없다는 뜻

---

😵 왜 헷갈렸을까?

1. 입력 좌표의 순서와 배열 접근 순서가 다름
   • 입력은 (y, x) 형태로 주어짐.
   • 하지만 배열 접근은 field[x][y]로 해야해서, (x, y) 순서를 먼저 떠올려서 헷갈림.
2. 가로/세로 개수(N, M)를 기준으로 좌표를 반대로 해석해서
   • M이 가로(열 개수) → y
   • N이 세로(행 개수) → x

근데 이름만 보면 가로(M) -> x, 세로(N) -> y 로 생각함

1. 2차원 배열에서 [행][열] 순서를 반대로 쓴 경우
   • JavaScript 배열은 field[row][col] 형식이니까
   • x를 행 (세로), y를 열 (가로)로 보면 field[x][y] - 하지만 대충 생각해서 field[y][x]로 쓰면… 당연히 인덱스 오류 발생

✅ 어떻게 바로 파악해야 할까 ?

1. 문제가 말하는 좌표 순서를 꼭 체크하기

입력: y x

• 이렇게 돼 있으면 → field[x][y]로 저장해야 됨
• 좌표가 (열, 행) 순서로 주어지는 거라 순서를 바꿔서 배열에 저장

2. 배열 구조 먼저 잡기

const field = Array.from({ length: N }, () => Array(M).fill(0));
// N: 세로 (행 수) → x 방향
// M: 가로 (열 수) → y 방향

무조건

• field[x][y] → x는 세로(행), y는 가로(열)

3. 좌표 범위 체크는 항상 >= 사용하기

if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;

헷갈릴 땐 직접 써보고 그려보기 !

M = 5, N = 3
좌표: (y, x) = (2, 1) 이면
배열에서는 field[1][2] = 1

---

풀이

let [T, ...input] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

let worm = 0;
let idx = 0;
const dx = [1, 0, -1, 0];
const dy = [0, 1, 0, -1];

// N: 세로 (행 개수) → 보통 x축으로 취급 (위아래 방향)
// M: 가로 (열 개수) → 보통 y축으로 취급 (좌우 방향)

while (idx < input.length) {
  let [M, N, K] = input[idx].split(" ").map(Number);
  const field = Array.from({ length: N }, () => Array(M).fill(0)); // 배추밭
  const visited = Array.from({ length: N }, () => Array(M).fill(0)); // 거리를 저장할 변수
  for (let j = idx + 1; j < K + idx + 1; j++) {
    const [y, x] = input[j].split(" ").map(Number);
    field[x][y] = 1;
  }
  for (let x = 0; x < N; x++) {
    for (let y = 0; y < M; y++) {
      if (field[x][y] == 1 && visited[x][y] == 0) {
        // 배추있고,방문 x
        bfs(x, y, visited, field);
      }
    }
  }
  idx += K + 1;
  console.log(worm);
  worm = 0;
}

function bfs(startX, startY, visited, field) {
  const queue = [[startX, startY]];
  visited[startX][startY] = 1;
  worm++;

  while (queue.length > 0) {
    const [x, y] = queue.shift();

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

      if (nx < 0 || nx >= field.length || ny < 0 || ny >= field[0].length)
        continue;

      if (field[nx][ny] == 0 || visited[nx][ny] == 1) continue;

      queue.push([nx, ny]);
      visited[nx][ny] = 1;
    }
  }
}

---

END