[Java Algorithm] 백준 1962 _ 그림

[문제]

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

입력
첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

출력
첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

 

[Algorithm]

모든 칸을 돌면서 1이면서 방문 X이면 그림 개수 +1

그 칸에서 bfs 탐색

모든 칸에서 반복 후 최종 값 반환

 

bfs 탐색 과정
1. 탐색 시작점을 큐에 넣고 방문 처리
2. 현재 그림의 넓이를 1로 초기화
3. 큐가 빌 때까지 반복
- 큐에서 칸 하나를 꺼냄
- 상하좌우 4방향 확인
→ 범위 내에 존재 + 1 + 아직 방문 X = 큐에 추가, 방문 처리, 넓이 + 1
4. 그림 넓이 반환

 

[자료 구조]

2차원 배열 : 도화지 정보 저장

방문 체크 배열 : 탐색 여부 확인

큐 : BFS 탐색을 위한 자료구조

방향 배열 : 상하좌우 이동을 위한 dx, dy 배열 → 외워두면 편함!

 

[Code]

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

public class Main {
    static int n, m;	// 도화지 세로, 가로
    static int[][] paper; // 2차원 도화지 배열
    static boolean[][] visited;	// 방문 여부
    static int[] dx = {-1, 1, 0, 0}; // 상하좌우
    static int[] dy = {0, 0, -1, 1};
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        paper = new int[n][m];
        visited = new boolean[n][m];
        
        // 도화지 배열 초기화
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                paper[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        int count = 0;    // 그림의 개수
        int maxArea = 0;  // 최대 넓이
        
        // 모든 칸 순회
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 1이고 아직 방문하지 않은 칸이면 새로운 그림 시작
                if (paper[i][j] == 1 && !visited[i][j]) {
                    count++;
                    int area = bfs(i, j);
                    maxArea = Math.max(maxArea, area);
                }
            }
        }
        
        System.out.println(count);
        System.out.println(maxArea);
    }
    
    // BFS로 연결된 그림의 넓이 구하기
    static int bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;
        int area = 1;
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int cx = current[0];
            int cy = current[1];
            
            // 상하좌우 4방향 탐색
            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                
                // 범위 체크 및 조건 확인
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if (paper[nx][ny] == 1 && !visited[nx][ny]) {
                        queue.offer(new int[]{nx, ny});
                        visited[nx][ny] = true;
                        area++;
                    }
                }
            }
        }
        
        return area;
    }
}

 

 

[+ Plus]

💡Queue 인터페이스

먼저 넣은 객체가 먼저 빠져나가는 FIFO 자료구조

Queue<E> queue = new LinkedList<E>();

 

offer : 주어진 객체 삽입

peek : 객체 하나 가져옴, 큐에서 제거 안함

poll : 객체 하나 가져옴, 큐에서 제거

 

PriorityQueue (우선순위 큐)

저장한 순서와 관계 없이 우선순위에 따라 꺼내는 순서가 정해진 큐