[백준 1926/자바] 그림

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

 

 

 

---

 

BFS 공부

✨ 참고
https://velog.io/@minjoott_dev/%EB%B0%B1%EC%A4%80-1926%EB%B2%88-%EA%B7%B8%EB%A6%BC-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-java

 

---

 

풀이

BFS를 이용하여 한 점에서 시작되는 그림의 넓이 파악

그림의 경계선 마주할 때까지 함수는 끝나지 않음

• 그림 정보 저장할 2차원 boolean 배열
• 방문 여부를 체크할 2차원 boolean 배열
• BFS 실행 시 사용할 queue

이중 for문을 이용하여 x, y값을 확인한 뒤,

해당 좌표가 도화지에서 색칠된 부분이고 아직 방문하지 않은 위치인 경우 BFS 실행

 

BFS 함수

1. 좌표에 방문 표시를 한 뒤 queue에 좌표 정보 삽입
   
   1. 그림 넓이 = 1 초기화
2. 근처 상하좌우 확인하기 위해 queue에서 좌표 정보 꺼내기
3. 해당 좌표의 근처 점들이 마찬가지로 색칠이 돼있고 방문하지 않은 점인 경우 방문 처리 후 queue에 삽입
   
   1. 그림 넓이 +1
4. while문을 이용하여 queue가 빌 때까지 위 과정 반복
5. 근처 좌표의 값이 모두 값이 0이거나 이미 방문한 좌표면 queue에 추가되는 값 X
   1. 그림이 끝난 것이므로 그림의 넓이를 확인할 수 있음
   2. while문 이후 전체 그림의 개수 +1

 

코드

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 Main {

    static int N, M;
    static boolean[][] paper;
    static boolean[][] isVisited;
    static int count = 0;
    static int max = 0;

    // 한 점에서 상하좌우 살피기 위함
    static int[] dx = {0, 0, -1, +1};
    static int[] dy = {-1, +1, 0, 0};

    static void BFS(int startY, int startX) {
        isVisited[startY][startX] = true;   // 방문 표시
        int area = 1;   // 면적 계산 위해 초기화

        // x, y 저장할 queue
        Queue<Integer> queueX = new LinkedList<>();
        Queue<Integer> queueY = new LinkedList<>();

        // queue에 현재 x, y 좌표값 삽입
        queueX.add(startX);
        queueY.add(startY);

        /**
         * 1) queue가 비어있지 않은 경우(그림이 끝나지 않은 경우)
         * 2) queue에서 값을 꺼내고
         * 3) 해당 좌표의 상하좌우 확인
         * 4) 그림이 존재하고(값이 1이고) 방문하지 않은 원소인 경우
         * 5) 방문 표시한 뒤 면적+1, queue에 해당 좌표 삽입
         *
         * queue가 빌 때까지(그림의 경계선을 만날 때까지) 위 과정 반복
         * 상하좌우가 모두 값이 0이거나 이미 방문한 좌표면 queue에 추가되는 값 X
         * 그림이 끝난 것이므로 그림의 넓이를 확인할 수 있음. 그리고 전체 그림의 개수+1
         */
        while (!queueX.isEmpty()) {
            // 아래 x, y 좌표를 기준으로 상하좌우 탐색
            int x = queueX.poll();
            int y = queueY.poll();

            for (int i = 0; i < 4; i++) {
                int nowX = x + dx[i];
                int nowY = y + dy[i];

                if (nowY < N && nowY >= 0 && nowX < M && nowX >= 0
                        && paper[nowY][nowX] && !isVisited[nowY][nowX]) {
                    area++;
                    isVisited[nowY][nowX] = true;
                    queueX.add(nowX);
                    queueY.add(nowY);
                }
            }
        }

        count++;    // 그림 개수 증가
        if (area > max) { // 가장 큰 넓이 확인
            max = area;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());   // 도화지 세로 크기
        M = Integer.parseInt(st.nextToken());   // 도화지 가로 크기

        paper = new boolean[N][M];  // 도화지
        isVisited = new boolean[N][M];  // 방문 표시

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                // 1로 표시된 부분은 도화지 배열에 true로 저장
                if (st.nextToken().equals("1")) {
                    paper[i][j] = true;
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                /**
                 * 1) x, y 좌표 확인 후
                 * 2) 그림이 그려져 있고
                 * 3) 아직 방문하지 않은 좌표면 BFS 실행
                 *
                 * 해당 좌표를 시작으로 그 그림의 넓이를 확인함
                 */
                if (paper[i][j] && !isVisited[i][j]) {
                    BFS(i, j);
                }
            }
        }

        sb.append(count).append('\n').append(max);
        System.out.println(sb);
    }

}