백준 1012번 유기농배추 문제풀이

문제출처 :

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

사고과정

1. 지렁이는 상,하, 좌,우 인접한 배추로 옮겨다니면서 배추를 보호할 수 있다.
2. 가장 최소한의 지렁이 갯수를 출력하는 문제이므로, bfs를 이용하여 Map을 순회하다가 배추를 마주하자마자 인접한 배추영역을 찾고 count를 1증가시키자.
3. 그럼 최종적으로 상하좌우로 인접한 배추들에 하나의 지렁이만 두는 격이다.

소스코드

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Baek1012 {
    static int tc;
    static int[][] canGo = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    static int[][] srcMap;
    static int cnt;
    static int n, m, cabbages;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        tc = Integer.parseInt(br.readLine());
        for (int i = 0; i < tc; i++) {
            cnt=0;
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            srcMap = new int[n][m];
            cabbages =Integer.parseInt(st.nextToken());
            for (int cabbage = 0; cabbage < cabbages; cabbage++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                srcMap[x][y]=1; // 맵에서 cabbage 영역표시하기
            }
            for (int j = 0; j < n; j++) {
                for(int k = 0; k < m; k++) {
                    if (srcMap[j][k] == 1) {
                        bfs(j,k);
                    }
                }
            }
            sb.append(cnt).append("\n");
        }
        System.out.println(sb.toString());
    }
    static void bfs(int i, int j){
        Queue<int[]> q = new LinkedList<int[]>();
        srcMap[i][j]=0;//일종의 방문표시
        cnt++;
        q.offer(new int[]{i, j});
        while (!q.isEmpty()) {
            int[] temp = q.poll();
            int x = temp[0];
            int y = temp[1];
            for (int[] next : canGo) {
                int nx = x+next[0];
                int ny = y+next[1];
                if(nx<0||ny<0||nx>=n||ny>=m)continue;//bfs를 수행하면서 맵밖의 영역으로 벗어난다면 continue
                if(srcMap[nx][ny]==0)continue;
                srcMap[nx][ny]=0;
                q.offer(new int[]{nx, ny});
            }
        }

    }
}

잘 이해가 안되는 부분이 있거나 소스코드에 문제가 있다면 댓글을 남겨주세요.