백준_현수막_14716

//알고리즘

1. 8방 체크 완전탐색문제.

2. 8방을 체크할 수 있는 dr, dc 배열을 만들고 시작함.

3. dfs를 돌리는데 방문배열을 따로 쓰지말고 기존의 map 배열을 초기화.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 현수막_14716 {

	static int M, N, map[][];
	static int[] dr = { -1, -1, -1, 0, 1, 1, 1, 0 };
	static int[] dc = { -1, 0, 1, 1, 1, 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());

		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());

		map = new int[M][N];

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int Ans = 0;
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if(map[i][j] == 1) {
					Ans++;
					dfs(i,j);
				}
			}
		}
		
		System.out.println(Ans);
//		print(map);

	}

	private static void dfs(int r, int c) {
		map[r][c] = 0;
		
		for (int k = 0; k < 8; k++) {
			int nr = r + dr[k];
			int nc = c + dc[k];
			
			if(nr<0 || nc < 0 || nr>= M || nc>=N) continue;
			if(map[nr][nc] ==1) {
				dfs(nr, nc);
			}
			
		}
		
	}

	private static void print(int[][] map) {
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();

		}
	}

}