백준 1012 : 유기농 배추

💡기본 정보

유형
: DFS/BFS
풀이 날짜
: 2025년 01월 22일 
풀이방법 한줄 요약
: 전체를 순환하면서 상하 좌우를 함께 체크하기 

 

💡문제에서 구해야 할 것

농약을 쓰지 않고 배추를 재배하기 위해 배추흰지렁이를 구입해 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 지렁이가 이동하며 이동이 가능해 보호를 받을 수 있음 

다음과 같이 배추가 심어져 있다면 배추가 모여있는 곳에는 배추흰지렁이가 한마리만 있으면 됨. 서로 인접해 있는 배추들이 몇군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있음

1 : 배추가 심어져있는 땅
0 : 배추가 심어져있지 않은 땅

- 입력 : 첫째 줄에는 테스트 케이스의 개수 T가 주어짐
            그 다음 줄부터 각각의 테스트 케이스에 대한
              첫째 줄에는 배추를 심은 배추밭의 가로길이 M , 세로 길이 N, 배추가 심어져있는 위치의 개수 K가 주어짐 
              그 다음 K줄에는 배추의 위치 X,Y가 주어짐 두 배추의 위치가 같은 경우는 없음
- 출력 : 각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력함

 

💡알고리즘 설계

- 배추가 심어져있는 MN 크기의 행렬을 만들어 배추가 심어져있으면 1 배추가 심어져있지 않으면 0 을 기록함

- 한 점에 만날 때마다 애벌레 갯수를 추가하고 상하좌우에 있는 배추도 함께 방문 기록(애벌레 하나만 있어도 충분해서) 

 

💡CODE

const fs = require("fs");
const input = fs.readFileSync(0,"utf8").toString().trim().split("\n");
const T = parseInt(input[0]);
const graph=input.map((v) => v.split(" ").map(Number));

let farm = [];
let visit = [];

const row=[0,0,-1,1];
const col=[-1,1,0,0];

function DFS(j,k,N,M){
    visit[j][k] = true;
    for(let i = 0;i<4;i++){
        newJ = j+col[i];
        newK = k+row[i];
        if(newJ >= 0 && newJ<N && newK>=0&& newK < M){
            if(farm[newJ][newK]===1&&visit[newJ][newK]===false){
                DFS(newJ,newK,N,M);
            }
        }
    }
}

for (let i = 0; i < T; i++) {
    let worm = 0;
  
    let [M, N, K] = graph.shift();
    farm = Array.from(Array(N), () => new Array(M).fill(0));
    visit = Array.from(Array(N), () => new Array(M).fill(false));
    while (K > 0) {
      K--;
      const [x, y] = graph.shift();
      farm[y][x] = 1;
    }
    for (let j = 0; j < N; j++) {
      for (let k = 0; k < M; k++) {
        if (farm[j][k] === 1 && visit[j][k] === false) {
          DFS(j, k, N, M);
          worm++;
        }
      }
    }
    console.log(worm);
  }

 

💡시간복잡도

 

💡 틀린 이유 & 틀린 부분 수정

예전에 풀었던 1051처럼 확인하는 로직을 생각했는데 그렇게 하면 구현이 어려워서 col과 row를 따로 지정해서 구현

 

💡 다른 풀이 or 기억할정보

farm = Array.from(Array(N), () => new Array(M).fill(0));

: MN크기의 그래프를 표현하고 0으로 초기화할 때