백준 - 1012번

 

풀이

 

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

 

public class Main {

 

      static int maxX = 0;

      static int maxY = 0;

      static int[][] field; // 농장 배열

      public static void main(String[] args) throws IOException {

            String str = "";

            String[] arr;

            int count = 0; // 배추 개수

            int earthwormCount = 0;

            int[] answer;

            BufferedReader br = new BufferedReader ( new InputStreamReader (System.in));

            int num = Integer.parseInt(br.readLine());

            answer = new int[num];

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

                  earthwormCount = 0;

                  str = br.readLine();

                  arr = str.split(" ");

                  maxX = Integer.parseInt(arr[0]);

                  maxY = Integer.parseInt(arr[1]);

                  field = new int[maxX][maxY];

                  count = Integer.parseInt(arr[2]);

                  // 배추 위치 할당

                  for(int j=0; j<count; j++) {

                        str = br.readLine();

                        arr = str.split(" ");

                        field[Integer.parseInt(arr[0])][Integer.parseInt(arr[1])] = 1;

                  }

                  // 지렁이 개수 찾기

                  for(int j=0; j<maxX; j++) {

                        for(int k=0; k<maxY; k++) {

                              if(field[j][k] == 1) {

                                    Find(j, k); // 재귀 실행

                                    earthwormCount++;

                              }

                        }

                  }

                  answer[i] = earthwormCount;

            }

            for(int i=0; i<answer.length; i++) {

                  System.out.println(answer[i]);

            }

      }

 

      private static void Find(int stateX, int stateY) {

            field[stateX][stateY] = 2;

            if(stateX == 0) {

                  if(field[stateX+1][stateY] == 1) {

                        Find(stateX+1, stateY);

                  }

            }else if(stateX == maxX-1){

                  if(field[stateX-1][stateY] == 1) {

                        Find(stateX-1, stateY);

                  }

            }else {

                  if(field[stateX+1][stateY] == 1) {

                        Find(stateX+1, stateY);

                  }

                  if(field[stateX-1][stateY] == 1) {

                        Find(stateX-1, stateY);

                  }

            }

            if(stateY == 0) {

                  if(field[stateX][stateY+1] == 1) {

                        Find(stateX, stateY+1);

                  }

            }else if(stateY == maxY-1) {

                  if(field[stateX][stateY-1] == 1) {

                        Find(stateX, stateY-1);

                  }

            }else {

                  if(field[stateX][stateY+1] == 1) {

                        Find(stateX, stateY+1);

                  }

                  if(field[stateX][stateY-1] == 1) {

                        Find(stateX, stateY-1);

                  }

            }

      }

}