[BOJ] 1012 유기농 배추 - JAVA

1. 문제

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

어떤 배추에 배추 흰 지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

---

2. 풀이

메인함수

• 배추가 있는 위치에 1을 입력했다.
• 그리고 bfs탐색 메서드가 불릴 때마다 cnt+1을 해주었다.

static int N,M;
static int[][] farm;
static int[][] deltas = {{0,1},{0,-1},{1,0},{-1,0}};//우좌하상, yx순
public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   int T = Integer.parseInt(in.readLine());
   StringBuilder sb = new StringBuilder();

   while(--T>=0){
      StringTokenizer st = new StringTokenizer(in.readLine());
      M = Integer.parseInt(st.nextToken());
      N = Integer.parseInt(st.nextToken());
      int K = Integer.parseInt(st.nextToken());

      farm = new int[N][M];

      for(int k=0;k<K;k++){
         st = new StringTokenizer(in.readLine());
         int x = Integer.parseInt(st.nextToken());
         int y = Integer.parseInt(st.nextToken());
         farm[y][x] = 1;
      }

      int cnt = 0;
      for(int i=0;i<N;i++){
         for(int j=0;j<M;j++){
            if(farm[i][j]==1) {
               bfs(new int[]{i,j});
               ++cnt;
            }
         }
      }

      sb.append(cnt).append("\n");

   }

   System.out.print(sb);
}

 

탐색 - BFS 이용

• 배추를 큐에 넣었다면 그 위치를 0으로 바꿔주었다. 원본을 굳이 보존할 필요 없는 문제이기 때문이다.

private static void bfs(int[] cabbage){
   Queue<int[]> queue = new LinkedList<>();
   queue.offer(cabbage);

   farm[cabbage[0]][cabbage[1]] = 0;

   while(!queue.isEmpty()){
      cabbage = queue.poll();

      for(int d=0;d<4;d++){
         int ni = cabbage[0]+deltas[d][0];
         int nj = cabbage[1]+deltas[d][1];
         if(ni>=0 && ni<N && nj>=0 && nj<M && farm[ni][nj]==1){
            queue.offer(new int[]{ni,nj});
            farm[ni][nj] = 0;
         }
      }

   }
}

---

3. 결과

2022.02.23 - [코딩테스트/BOJ] - [BOJ] 2667 단지번호 붙이기 - JAVA 문제와 정말 비슷한 문제였다.