[백준 1926] 그림

문제설명

문제 풀기
참고 링크

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

생각정리

그래프 탐색으로 풀 수 있는 문제이다. (BFS로 풀어보도록 하겠다)
이 문제에서 출력해야하는 것은 2가지 인데,

• 그림의 개수
• 가장 넓은 그림의 넓이

BFS 탐색의 과정은 다음과 같다.

1. 첫번째 탐색요소에 방문표시를 하고, queue에 넣는다.
   queue가 비어있지 않는 동안 (= queuer가 빌때가지) 다음을 진행한다.
2. queue에서 첫번째 요소를 꺼낸다.
3. 해당 요소의 주변을 방문하며 다음을 진행한다.

• 방문하지 않았다면 방문 표시를 하고 queue에 넣는다.
• 이미 방문했다면, 넘어간다.

정리된 생각에 대한 논리

• 그림의 개수는 새롭게 탐색을 시작하는 횟수이다.
• 가장 넓은 그림의 넓이는 queue에서 요소를 빼낸 횟수이다. (poll)

완성

import java.io.*;
import java.util.*;

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

public class BOJ1926{
	
	static int map[][];
	static boolean visited[][];
	static int dx[] = {-1, 1, 0, 0};
	static int dy[] = {0, 0, -1, 1};
	static int n = 0;
    static int m = 0;
    static Queue<Position> queue = new LinkedList<>();

	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());
        
		map = new int[n][m];
		visited = new boolean[n][m];
		for(int i=0; i<n; i++) {
			String[] newStr = br.readLine().split(" ");

			for(int j=0; j<m; j++) {
				map[i][j] = Integer.parseInt(newStr[j]);
			}
		}
		
		int count = 0;
		int c = 0;
        int max = 0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {

                if(visited[i][j] == false && map[i][j] == 1) {
                    Position p = new Position(i, j);
                    visited[i][j] = true;
                    queue.add(p);
                    count++;
                }
                    
                while(!queue.isEmpty()) {

                    Position output = queue.poll();
                    c++;

                    for(int k=0; k<4; k++) {
                        int nextX = output.x + dx[k];
                        int nextY = output.y + dy[k];
                        
                        if(nextX<0 || nextY<0 || nextX>=n || nextY>=m) 
                            continue;
                        else if(visited[nextX][nextY] == true || map[nextX][nextY] == 0) 
                            continue;
                        else {
                            visited[nextX][nextY] = true;
                            
                            queue.add(new Position(nextX, nextY));
                        }
                    }
                }

            max = Math.max(max, c);
            c = 0;

			}
		}
		
		System.out.println(count);
        System.out.println(max);
	}
	
	
}