백준_1012번_유기농 배추_자바

백준_1012번_유기농 배추_자바

 

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

1012번: 유기농 배추

 

이번 문제는 DFS/BFS로 풀이 가능한 문제이며, DFS로 풀이하였습니다.

 

입력 사항 -  

첫째줄에 테스트케이스의 횟수

둘째줄에 배추밭의 가로 세로 길이와 배추의 개수

그 이후엔 배추의 위치가 입력됩니다.

 

주의 사항  - 

깊이 탐색하는데에 있어서 배추가 있는 모든 위치에서 시작해보아야하며,

가로 세로에 붙어있는 배추는 하나로 계산합니다.

 

풀이 방식 -

저의 경우 배추밭의 경우가 1과 0 밖에 없기에  boolean배열을 만들어서 1을 true로 입력 받았습니다.

같은 부분을 재 확인(?)해야할 경우는 없기에 체크 배열을 따로 만들지 않고,

체크 후에는 원본 배열을 false로 변환 하였습니다. 

 

 

로직 - 

 

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

public class Main {

    static int n;
    static int m;
    static int cnt;
    static boolean[][] arr;
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};




    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());

        for (int i = 0; i < n; i++) {

            cnt = 0;
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            arr = new boolean[x+1][y+1];

            m = Integer.parseInt(st.nextToken());

            for (int j = 0; j < m; j++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                arr[a][b] = true;

            }
            for (int j = 0; j < arr.length; j++) {
                for (int k = 0; k < arr[j].length; k++) {
                    if(arr[j][k]==true){
                        dfs(j,k);
                        cnt++;
                    }
                }
            }
            System.out.println(cnt);
        }
        
    }

    private static void dfs(int c,int d) {
        if(c== arr.length && d == arr[0].length){
            return;
        }

        for (int i = 0; i < 4; i++) {
            if( c+dx[i]>=0 && d+dy[i]>=0&& c+dx[i] < arr.length && d+dy[i] < arr[0].length ) {
                if(arr[c+dx[i]][d+dy[i]]==true){
                    arr[c+dx[i]][d+dy[i]]=false;
                    dfs(c+dx[i],d+dy[i]);
                }
            }
        }
    }
    
    
}