문제

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

풀이

N X M 배열이 주어졌을 때 이어진 그림의 개수와 그림의 최대 넓이를 출력하는 문제이다.
그림의 넓이는 상,하,좌,우로만 이어진 부분의 합이므로 bfs로 넓이를 탐색하여 구할 수 있다.

1. N X M 배열을 반복문을 돌려 방문되지 않았고 1인 위치를 시작지점으로 bfs를 수행한다.
2. bfs를 통해 그림의 넓이를 구하고 최대 넓이를 저장한다. 또한 bfs의 횟수는 그림의 개수와 같으므로 그림의 개수를 1 추가한다.
3. 그림의 개수와 그림의 최대 넓이를 출력한다.

class Pair{
		int y;
		int x;
		Pair(int y, int x){
			this.y = y;
			this.x = x;
		}
	}

각 좌표의 위치를 관리하기 위해 Pair 클래스를 별도로 선언하였다.

코드

public class Main {

	int[][] board;
	boolean[][] visited;
	int N,M;
	int count = 0, maxRes = 0;
	
	int[] dy = {1,-1,0,0};
	int[] dx = {0,0,-1,1};
	
	class Pair{
		int y;
		int x;
		Pair(int y, int x){
			this.y = y;
			this.x = x;
		}
	}
	
	int BFS(int y, int x) {		
		visited[y][x] = true;
		Queue<Pair> queue= new LinkedList<>();
		queue.add(new Pair(y,x));
		int cnt = 0;
		
		while(!queue.isEmpty()) {
			int yy = queue.peek().y;
			int xx = queue.peek().x;
			queue.remove();
			cnt++;
			
			for(int i = 0; i < 4;i++) {
				int ny = yy + dy[i];
				int nx = xx + dx[i];				
				
				if(ny < 1 || ny > N || nx < 1 || nx > M) {
					continue;
				}
				if(visited[ny][nx] == true || board[ny][nx] == 0) {
					continue;
				}
								
				visited[ny][nx] = true;				
				queue.add(new Pair(ny, nx));
			}
		}
		
		return cnt;
	}	
	
	void solution() throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		board = new int[N + 2][M + 2];
		visited = new boolean[N + 2][M + 2];			
		
		for(int i = 1; i <= N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 1;j <= M;j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
				
		for(int i = 1;i<=N;i++) {
			for(int j = 1; j<=M;j++) {
				if(visited[i][j] == false && board[i][j] == 1) {
					count++;
					maxRes = Math.max(BFS(i, j), maxRes);
				}
			}
		}			
		System.out.println(count + "\n" + maxRes);
	}
	
	public static void main(String[] args) throws Exception{
		new Main().solution();
	}
}