[BOJ/백준] 1926 그림 (S1)

문제

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

풀이

그림의 개수와 넓이가 가장 넓은 그림의 넓이를 출력해야 한다.

graph를 순회하면서 1(색칠이 칠해진 곳, 그림의 시작점)을 만나면, 해당 위치의 visited[][](방문 여부)를 확인하고 방문한 적이 없으면 bfs()를 실행하여 동서남북으로 연결된 칸수를 방문처리하고, 연결된 1의 개수를 area 리스트에 추가한다. 추가로 bfs() 횟수를 ++하여 그림의 개수를 파악한다.

graph의 모든 지금을 방문하였다면 area 리스트를 정렬하여 가장 큰 값을 출력한다.

Code

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

public class Main {

    static int n, m;
    static boolean[][] visited;
    static int[][] graph;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static List<Integer> area;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        graph = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        visited = new boolean[n][m];
        area = new ArrayList<>();

        int pictureCnt = picCnt();
        int maxPicArea = area.isEmpty() ? 0 : Collections.max(area);  // 그림이 아예 없는 경우 Collections.max()를 사용하면 NoSuchElementException가 발생하므로, 빈 경우 0을 저장하도록 처리해야 함.
        bw.write(pictureCnt + "\n" + maxPicArea);
        bw.flush();
        bw.close();
    }

    private static int picCnt() {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (graph[i][j] == 1 && !visited[i][j]) {
                    bfs(i, j);
                    cnt++;
                }
            }
        }
        return cnt;
    }

    private static void bfs(int x, int y) {
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        queue.add(new int[] {x, y});
        visited[x][y] = true;  // 방문 처리
        int cnt = 1;  // 시작 위치의 그림 첫부분부터 카운트

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int cx = current[0];
            int cy = current[1];

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];

                if (nx >=0 && ny >= 0 && nx < n && ny < m && !visited[nx][ny] && graph[nx][ny] == 1) {  // 다음 위치가 범위 내에 있고, 방문하지 않은 곳이면서, 1인곳
                    visited[nx][ny] = true;  // 방문 처리
                    queue.add(new int[] {nx, ny});  // 다음 좌표 추가
                    cnt++;
                }
            }
        }
        area.add(cnt);
    }
}