백준 1926 그림 / JAVA

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

1926번: 그림

 

> 풀이(BFS)

/*
 * 백준 1926 그림
 * #실버1
 * #BFS
 */
public class boj_1926 {

	static int n,m;
	static int[] dx = {1, 0, -1, 0}; // 하 우 상 좌
	static int[] dy = {0, 1, 0, -1}; // 하 우 상 좌
	static int[][] arr;
	static int cnt = 0;
	static int maxArea = 0;
	static boolean[][] visited;
	static class Point {
		int x,y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		arr = new int[n][m];
		visited = new boolean[n][m];
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < m; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if(!visited[i][j] && arr[i][j] == 1) {
					cnt++;
					BFS(i,j);
				}
			}
		}
		System.out.println(cnt);
		System.out.println(maxArea);
	}
	
	public static void BFS(int x, int y) {
		Queue<Point> queue = new LinkedList<>();
		queue.offer(new Point(x,y));
		visited[x][y] = true;
		
		int area = 1;
		while(!queue.isEmpty()) {
			Point point = queue.poll();
			for(int i = 0; i < 4; i++) {
				int nx =  point.x + dx[i];
				int ny =  point.y + dy[i];
				if(nx >= 0 && nx < n && ny >= 0 && ny < m) {
					if(!visited[nx][ny]) {
						visited[nx][ny] = true;
						if(arr[nx][ny] == 1) {
							area++;
							queue.offer(new Point(nx,ny));
						}
					}
				}
			}
		}
		maxArea = Math.max(maxArea, area);
	}

}