[Algorithm/Java] 백준 1926 그림

문제

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

---

풀이

위 예제에서의 그림은 4개이며 가장 넓이가 넓은 그림은 오른쪽 하단에 위치한 넓이 9인 연두색 그림인 것을 알 수 있습니다. 1로 연결된 것을 하나의 그림으로 정의하므로 BFS를 진행하면서 그림의 넓이와 갯수를 구하면 됩니다.

소스코드

public class BOJ_S1_1926_그림 {
	
	static int n,m,screen[][];
	static int[] dr = {-1,1,0,0}; // 4방탐색 시 변하는 row값
	static int[] dc = {0,0,-1,1}; // 4방탐색 시 변하는 column값
	static int max;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		screen = new int[n][m];
		
		for(int r=0;r<n;r++) {
			st = new StringTokenizer(br.readLine()," ");
			for(int c=0;c<m;c++) {
				screen[r][c] = Integer.parseInt(st.nextToken());
			}
		} // 입력 완료
		
		boolean[][] visited = new boolean[n][m]; // 방문 체크를 위한 boolean형 2차원 배열 생성
		max = 0;
		int cnt = 0;
		for(int r=0;r<n;r++) {
			for(int c=0;c<m;c++) {
				if(!visited[r][c] && screen[r][c] == 1) { // 방문하지 않았고 그림이라면
					bfs(new Integer[]{r,c},visited); // BFS 탐색
					cnt++; // 그림 갯수 증가
				}
			}
		}
		
		System.out.println(cnt);
		System.out.println(max);

	}
	
	private static void bfs(Integer[] start, boolean[][] visited) {
		Queue<Integer[]> q = new LinkedList<>();
		visited[start[0]][start[1]] = true;
		
		q.offer(start);
		int size = 1;
		
		while(!q.isEmpty()) {
			Integer[] cur = q.poll();
			
			for(int d=0;d<4;d++) {
				int nr = cur[0] + dr[d];
				int nc = cur[1] + dc[d];
				
				if(nr < 0 || nr >= n || nc<0 || nc>=m ) continue; // 범위를 벗어난 경우
				if(visited[nr][nc] || screen[nr][nc] != 1) continue; // 이미 방문했거나 그림이 아닌 경우
				
				visited[nr][nc] = true;
				size++;
				q.offer(new Integer[] {nr,nc});
			}
		}
		if(size > max) { // 현재 탐색하고 있는 그림의 넓이가 최대라면
			max = size; // 최댓값 업데이트
		}
	}

}