[BOJ 백준] 1926: 그림 (자바 | Java)

[BOJ 백준] 1926: 그림

---

1. 문제

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

• BFS를 활용하는 기본 문제이다.
  BFS에 대한 개념을 가장 잘 적용할 수 있는 문제 같다.

---

2. PS

값이 1이면 색칠된 부분이므로 모든 그림을 돌면서 1이거나 방문하지 않은 그림들을 체크하며 처리하면 된다.
1. 모든 그림을 2차원 배열에 담아준다. (StringTokenize를 이용)
2. 큐를 이용하여 연결된 그림들을 모두 찾아준다. BFS
2.1 큐에 방문하지 않았거나 1인 그림을 넣는다.
2.2 원소 꺼내고 해당 원소를 기준으로 상, 하, 좌, 우 탐색(델타를 이용)을 하여 1인 그림을 다시 큐에 담고, 꺼내며 위 작업을 반복한다. 델타를 활용한 탐색

• 배열의 끝에 도달하거나 벗어나게 되는 점을 유의하며 예외처리 해줘야한다.

3. 풀이

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_1926 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] arr = new int[n][m];
        boolean[][] visit = new boolean[n][m];
        Queue<Point> queue = new LinkedList<>();

        // 오른쪽, 아래, 왼쪽, 위
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};

        // 배열 세팅
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int count = 0;
        int area = 0;
        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 0 이거나 방문 했던 곳이면 패스
                if (arr[i][j] == 0 || visit[i][j]) {
                    continue;
                }
                count++;
                queue.offer(new Point(i, j)); // java.awt.Point 클래스 활용
                visit[i][j] = true;
                area = 0;
                while (!queue.isEmpty()) {
                    Point p = queue.poll();
                    area++;
                    for (int k = 0; k < 4; k++) {
                        int x = p.x + dx[k];
                        int y = p.y + dy[k];
                        if (x < 0 || x >= n || y < 0 || y >= m) {
                            continue;
                        }
                        if (arr[x][y] == 1 && !visit[x][y]) {
                            queue.offer(new Point(x, y));
                            visit[x][y] = true;
                        }
                    }
                }
                if (area > maxArea) {
                    maxArea = area;
                }
            }
        }
        System.out.println(count);
        System.out.println(maxArea);
    }
}