BOJ 1926. 그림

BOJ 1926. 그림

풀이

2차원 배열이 주어지고, 배열에서 1로 연결된 그림의 갯수와 가장 큰 그림의 넓이를 구하는 문제이므로 BFS(너비 우선 탐색)을 사용하여 문제를 풀 수 있다.

N을 행의 길이, M을 열의 길이라 할 떄
2중 for 문으로 모든 보드를 확인하므로 O(NM)으로 모든 탐색을 완료할 수 있다.

각 그림의 시작점을 확인하기위해
2중 for문을 돌며 board의 좌표가 1이고 방문한 적이 없는지 확인한다.
각 그림의 시작점이라면 상하좌우를 탐색하여 그림의 size를 구하고, 방문한 적이 있는지를 체크한다.

각 시작점의 개수도 체크하여 그림의 개수를 알 수 있다.

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);

        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};

        int[][] board = new int[n + 1][m + 1];
        int[][] visit = new int[n + 1][m + 1];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        Queue<int[]> queue = new LinkedList<>();

        int count = 0;
        int max = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 1 && visit[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                    visit[i][j] = 1;
                    count++;

                    int size = 0;
                    while (!queue.isEmpty()) {
                        int[] p = queue.peek();
                        queue.poll();
                        size++;
                        for (int k = 0; k < 4; k++) {
                            int x = p[0] + dx[k];
                            int y = p[1] + dy[k];
                            if (x < 0 || x >= n || y < 0 || y >= m) continue;
                            if (visit[x][y] == 1 || board[x][y] != 1) continue;
                            visit[x][y] = 1;
                            queue.offer(new int[]{x, y});
                        }
                    }
                    if (max < size) max = size;
                }
            }
        }

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