<Algorithm> 30. 1012번 유기농 배추

1. 1012번 유기농 배추

• DFS를 이용해서 영역 구하는 간단한 문제

• Arrays.fill 함수를 이용하면 쉽게 초기화를 할 수 있다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer;   public class Main {          static boolean[][] visited;     static int count;     public static void main(String[] args) throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;         int T = Integer.parseInt(br.readLine());          ArrayList<Object> ans = new ArrayList<Object>();                  for(int k = 0; k < T; k++) {             count = 0;             st = new StringTokenizer(br.readLine());                          int row = Integer.parseInt(st.nextToken());             int col = Integer.parseInt(st.nextToken());             int N = Integer.parseInt(st.nextToken());                          int[][] arr = new int[row][col];             visited = new boolean[row][col];                          for(int i = 0; i < row; i++) {                                 Arrays.fill(arr[i], 0);             }                          for(int i = 0; i < N; i++) {                 st = new StringTokenizer(br.readLine());                 int x = Integer.parseInt(st.nextToken());                 int y = Integer.parseInt(st.nextToken());                                  arr[x][y] = 1;             }                                   for(int i = 0; i < row; i++) {                 for(int j = 0; j < col; j++) {                     if(!visited[i][j] && arr[i][j] == 1) {                         dfs(i, j, row, col, arr);                         count++;                     }                 }             }             ans.add(count);         }                  for(Object obj:ans)             System.out.println(obj);     }          public static void dfs(int x, int y, int row, int col, int[][] arr) {         visited[x][y] = true;         int[] dx = {0, 0, 1, -1};         int[] dy = {1, -1, 0, 0};                  for(int i = 0; i < dx.length; i++) {             int nx = x + dx[i];             int ny = y + dy[i];                          if(nx >= 0 && ny >=0 && nx < row && ny < col) {                 if(!visited[nx][ny] && arr[nx][ny] == 1) {                         dfs(nx, ny, row, col, arr);                 }             }                      }              }      }   Colored by Color Scripter

cs