백준 - 1926번(그림)

문제 출처: https://www.acmicpc.net/problem/1926

문제

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    private static int[][] directions = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }, };
    private static int n, m;
    private static int[][] art;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        n = Integer.parseInt(tokenizer.nextToken()); // 세로(행)
        m = Integer.parseInt(tokenizer.nextToken()); // 가로(열)

        art = new int[n][m];
        boolean[][] visited = new boolean[n][m];

        int cnt = 0; // 그림의 개수
        int res = 0; // 최댓값

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

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (art[i][j] == 1 && !visited[i][j]) {
                    res = Math.max(res, bfs(visited, i, j));
                    cnt++;
                }
            }
        }

        System.out.println(cnt + "\n" + res);
    }

    private static int bfs(boolean[][] visited, int y, int x) {
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] { y, x });

        int cnt = 0;

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0];
            int c = curr[1];

            if (visited[r][c]) continue;

            visited[r][c] = true;
            cnt++;

            for (int i = 0; i < 4; i++) {
                int dy = r + directions[i][0];
                int dx = c + directions[i][1];

                if (dy >= 0 && dy < n && dx >= 0 && dx < m) {
                    if (art[dy][dx] == 1 && !visited[dy][dx]) queue.offer(new int[] { dy, dx });
                }
            }
        }

        return cnt;
    }

}

• 코딩테스트를 준비하며 복습을 진행하고 있다.
• 아직 모르는 알고리즘이 많이 있지만, 기초 알고리즘을 다시 정리해본다.
• BFS 알고리즘을 적용한 아주 쉬운 문제였다. 그러나, 처음에 방문 처리 조건을 잘못 주어서 답이 나오지 않았다. 너무 쉽다고 생각한 나머지 안일하게 생각한 것 같다.