[BOJ] 백준 1012 - 유기농 배추 (자바)

윾기농 배추 문제

맨처음 런타임 에러가 나길래 뭐지 하고 문제를 다시 보니까

배추밭이 N*N이 아니라 N*M 이더라.... 

호다닥 수정하고 나니 정답!

+ BufferedReader를 사용했는데 String[] 배열을 통해서 값을 받아오는것 밖에 없나 싶더라.

풀이

1. 좌표 (0,0) 부터 (N,N) 까지 하나씩 살펴본다.

2. 배추가 있을경우(1일경우) DFS , BFS를 사용하여 상,하,좌,우에 배추도 같이 제거한다. (붙어있다면 한번에 제거 할 수 있기 때문)

3. 한번 수확하러 들어갈때마다 +1 씩 더해준다. (주변에 있는 배추 수확은 덧셈을 안해도 된다.)

소스

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
 
class Main {
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, 1, 0, -1 };
    static int[][] arr;
    static int N;
    static int M;
 
    public static void main(String[] args) throws Exception {
        //BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int T = Integer.parseInt(br.readLine());
        for (int Testcase = 0; Testcase < T; Testcase++) {
            String str[] = br.readLine().split(" ");
            M = Integer.parseInt(str[0]);
            N = Integer.parseInt(str[1]);
            int K = Integer.parseInt(str[2]);
            int count = 0;
            arr = new int[N][M];
            for (int i = 0; i < K; i++) {
                str = br.readLine().split(" ");
                arr[Integer.parseInt(str[1])][Integer.parseInt(str[0])] = 1;
            }
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (arr[i][j] != 0) {
                        DFS(i, j);
                        //배추 수확
                        count++;
                    }
                }
            }
 
            System.out.println(count);
 
        }
    }
 
    public static void DFS(int X, int Y) {
 
        for (int i = 0; i < 4; i++) {
            //다음 방문지 nextX,와 nextY
            int nextX = X + dx[i];
            int nextY = Y + dy[i];
 
            //nextX, nextY가 범위를 벗어난다면 그냥 통과한다.
            if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
                continue;
            }
            //다음 방문할 값이 0 이라면 그냥 통과한다.
            if (arr[nextX][nextY] == 0) {
                continue;
            }
            //방문한점은 0으로 바꿔준다.
            arr[nextX][nextY] = 0;
            DFS(nextX, nextY);
        }
    }
 
}