[백준]1012 유기농 배추

오 웬일로 한번에 성공 !!! dfs로 풀었다. bfs로도 한번 풀어봐야겠다.

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 Main_1012 {
    static int M, N, K;
    static int count;

    static boolean[][] dfs;
    static boolean[][] visit;

    public static void main(String[] args) throws IOException {
        Queue<Integer> q = new LinkedList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.valueOf(br.readLine());
        for (int i = 0; i < testCase; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            M = Integer.valueOf(st.nextToken());        // 배추밭 가로줄
            N = Integer.valueOf(st.nextToken());        // 배추밭 세로줄
            K = Integer.valueOf(st.nextToken());        // 배추가 심어진 갯수

            dfs = new boolean[M + 1][N + 1];            // 배추가 심어진 곳을 알기위한 배열
            visit = new boolean[M + 1][N + 1];          // 카운트 체크를 위한 배열

            for (int j = 0; j < K; j++) {
                StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
                int x = Integer.valueOf(st2.nextToken());
                int y = Integer.valueOf(st2.nextToken());
                dfs[x][y] = true;
            }
            count = 0;
            for (int a = 0; a < M; a++) {
                for (int b = 0; b < N; b++) {
                    if(dfs[a][b]) {
                        dfs(a, b, true);
                    }
                }
            }
            q.offer(count);
        }
        while (!q.isEmpty()) {
            System.out.println(q.poll());
        }
    }
    public static void dfs(int x, int y, boolean start) {
        if(!visit[x][y]) {
            visit[x][y] = true;
            if(start) {
                count++;
            }

            // 호출 된 위치와 인접한 위치 찾기
            if(x-1 > -1 && dfs[x-1][y]) {
                // 상
                dfs(x - 1, y, false);
            }
            if(x+1 < M && dfs[x+1][y]) {
                // 하
                dfs(x + 1, y, false);
            }
            if(y-1 > -1 && dfs[x][y-1]) {
                // 좌
                dfs(x, y - 1, false);
            }
            if(y+1 < N && dfs[x][y+1]) {
                // 우
                dfs(x, y + 1, false);
            }
        }
    }
}

👩‍💻 풀이
어제 풀었던(=풀이를 참고했던) 문제 덕분에 좌표를 떠올릴 순 있었으나 코드에 적용하는건 아무래도 익숙치않아서 그냥 내 방식으로 풀어봤다!
일단 배추가 심어져있는 배추밭을 배열 안에 boolean 값으로 모두 담아주고 배추가 심긴 곳부터 인접한 위치를 찾아야 하기 때문에 for문을 통해 배추가 심어져있는 위치만 dfs 함수를 호출했다.
배추벌레는 배추들이 인접해있으면 한마리만 있어도 되므로, 호출된 배추밭 위치에서 인접한 배추 위치는 카운팅하지 않으려고 인자값으로 start라는 boolean 값을 추가해줬다.
dfs 함수 내에서 불려진 배추밭은 카운팅 되지 않게 되고, 그럼 필요한 배추벌레 카운트 완료 ~~!!!

또 나만 이해하는 풀이일까..?🥲 암튼 ,, bfs로도 풀어보고 그땐 풀이를 좀 더 자세하고 이해하기 쉽게 적어봐야겠다!