본문 바로가기

백준

BOJ[JAVA] 1012 유기농배추

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

 

1012번: 유기농 배추

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 

www.acmicpc.net

import java.io.*;
import java.util.StringTokenizer;

public class Main {
     final static int MAX = 50 + 10; // 최대 50 + 여분 (10)
    static boolean map[][];
    static boolean visited [][];
    static int T, N, M, K;
    // y, x를 기준으로 (-1, 0) 이면 위, (1, 0) 이면 아래, (0, -1) 이면 왼쪽, (0, 1) 이면 오른쪽
    static int [] dirY = {-1, 1, 0 ,0};
    static int [] dirX = {0, 0, -1 ,1};

    static void dfs(int y, int x) { // 좌표와 배열의 차이로 x,y 반대로 들어감
        visited[y][x] = true;
        for (int i = 0; i < 4; i++) {
            int newY = y + dirY[i]; // 다음 방문 지점
            int newX = x + dirX[i];

            // 새 방문 지점에 배추가 존재하며, 방문한 적 없음
            if (map[newY][newX] && visited[newY][newX] == false){
                dfs(newY, newX);
            }
        }

//        dfs(y + 1, x); // 아래인 지점 방문
//        dfs(y - 1, x); // 위
//        dfs(y, x - 1); // 왼쪽
//        dfs(y, x + 1); // 오른쪽
    }

    public static void main(String[] args) throws IOException {
        // 0. 입력 및 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        T = Integer.parseInt(br.readLine()); // 테스트 케이스의 개수

        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken()); // 가로
            N = Integer.parseInt(st.nextToken()); // 세로
            K = Integer.parseInt(st.nextToken()); // 배추가 심어져 있는 위치의 개수

            map = new boolean[MAX][MAX];
            visited = new boolean[MAX][MAX];

            // 1. map 정보 반영
            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[y + 1][x + 1] = true;
            }

            // 2. dfs
            int answer = 0;
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++) {

                    // map[i][j] 지점에 배추가 존재하는지, 방문하지 않았는지
                    if (map[i][j] && visited[i][j] == false) {
                        answer++; // 지렁이 1마리 소비
                        dfs(i, j);
                    }
                }
            }

            // 3. 출력
            bw.write(String.valueOf(answer));
            bw.newLine();
        }
        bw.close();
        br.close();
    }   
}

'백준' 카테고리의 다른 글

BOJ[JAVA] 6603 로또  (0) 2023.09.10
BOJ[JAVA] 1946번 신입 사원  (1) 2023.08.27
BOJ[JAVA] 2615 오목  (0) 2023.08.21
BOJ[JAVA] 4949 균형잡힌 세상  (0) 2023.07.31
BOJ[JAVA] 2607 비슷한 단어  (0) 2023.07.31