1926 그림 JAVA

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

1926번: 그림

 

이번 문제는 BFS의 가장 기본적인 문제다.

아래의 코드를 간략히 설명하자면,

• dx, dy배열을 사용하는 이유는 (curX, curY) 좌표 기준으로 동서남북에 있는 원소를 현명하게 처리할 수 있기 때문이다.
• 시작점이 (0,0)이 아닐 수 있으니, 시작점이 될 수 있는 요소를 모두 찾아야 한다. 따라서 vis 배열에서 아직 방문하지 않았고, matrix 배열에서 요소가 1인 숫자를 시작점으로 간주한다.
• Q에서 값을 꺼내는 횟수는 곧 그림의 넓이가 된다. -> 최대 넓이를 구하는 건 매우 간단하다.
• 시작점을 찾은 횟수는 곧 그림의 개수가 된다.

조심해야 할것은 

• 큐에 요소를 넣을 때 방문 기록을 남겨야지, 뺄 때 방문 기록을 남기면 안된다.
• 주석에서 말해두었지만, from~end 사이의 코드들이 순서가 바뀌면 절대 안된다.
• 시작점을 방문하는 것도 마찬가지로 방문기록을 꼭 넣어줘야 한다. 그렇지 않으면, 의도치 않은 값이 도출될 수 있다.

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

public class Dev1926 {
    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 = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());

        int[][] matrix = new int[x][y];
        boolean[][] vis = new boolean[x][y];
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};

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

        Queue<Pair<Integer>> Q = new ArrayDeque<>();
        int maxArea = 0;
        int cnt = 0;
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (matrix[i][j] == 1 && !vis[i][j]) {
                    cnt++;
                    vis[i][j] = true;
                    Q.add(new Pair<>(i, j));

                    int tmp = 0;
                    while (!Q.isEmpty()) {
                        Pair<Integer> cur = Q.remove();
                        tmp++;
                        for (int k = 0; k < 4; k++) {
                            int nx = cur.x + dx[k];
                            int ny = cur.y + dy[k];
                            // from 여기의 순서가 바끼면 안됨
                            if(nx < 0 || ny < 0 || nx >= x || ny >= y) continue;
                            if(matrix[nx][ny] == 0 || vis[nx][ny]) continue;
                            // end
                            Q.add(new Pair<>(nx, ny));
                            vis[nx][ny] = true;
                        }
                    }
                    maxArea = Math.max(maxArea, tmp);
                }
            }
        }
        bw.write(cnt + "\n" + maxArea);
        bw.flush();
        bw.close();
    }

    static class Pair<T> {
        T x, y;
        public Pair(T x, T y) {
            this.x = x;
            this.y = y;
        }
    }
}