[BOJ/Java] 그림 (1926)

그림 (1926)

1. 문제 분석

문제 개요

• 주어진 2차원 배열에서 그림의 개수와 가장 큰 그림의 크기를 찾는 문제이다. 그림은 연결된 1의 집합으로 정의된다.

입력 형식

• 첫 번째 줄에는 배열의 행의 크기 n과 열의 크기 m이 주어진다.
• 다음 n개의 줄에는 m개의 정수가 주어지며, 각 정수는 0 또는 1이다. 1은 그림의 부분을 의미한다.

출력 형식

• 그림의 개수와 가장 큰 그림의 크기를 출력한다.

2. 알고리즘 종류

• DFS(깊이 우선 탐색) 알고리즘을 사용하여 문제를 해결한다. 이 알고리즘을 사용하여 그림을 탐색하고 각 그림의 크기를 계산한다.

3. 주요 부분 및 코드 작성 방법

1. DFS(깊이 우선 탐색) 사용

• DFS를 사용하여 그림의 각 부분을 탐색한다. 방문한 셀을 기록하고, 연결된 셀을 재귀적으로 탐색하여 그림의 크기를 계산한다.

2. 입력 처리 및 배열 초기화

• 배열의 크기를 입력받고, 그림 정보를 2차원 배열에 저장한다. 방문 여부를 기록할 배열을 초기화한다.

3. 그림 개수 및 크기 계산

• 그림이 있는 셀을 찾고, DFS를 통해 그림의 크기를 계산한다. 그림의 개수와 최대 그림의 크기를 저장하여 출력한다.

4. 코드 설명

(1) 메인 함수 (main)

• 입력 처리
  • 입력을 읽고 배열을 초기화한다.
• BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 위한 BufferedReader 객체 생성 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()); // 그림 정보 입력 } }
• DFS를 통한 탐색
  • 각 그림의 개수와 크기를 계산한다.
• int cnt = 0; // 그림의 개수 List<Integer> sizes = new ArrayList<>(); // 각 그림의 크기를 저장하는 리스트 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (paper[i][j] == 1 && !visited[i][j]) { // 그림이 있는 셀을 발견한 경우 max = 1; // 현재 그림의 크기를 1로 초기화 dfs(i, j); // DFS로 그림의 크기를 계산 sizes.add(max); // 그림의 크기를 리스트에 추가 cnt++; // 그림 개수 증가 } } }
• 결과 출력
  • 그림의 개수와 최대 크기를 출력한다.
• if (cnt == 0) { System.out.println(cnt + "\n" + 0); // 그림이 없는 경우 } else { System.out.println(cnt + "\n" + Collections.max(sizes)); // 그림의 개수와 최대 크기 출력 }

(2) DFS 함수 (dfs)

• 초기화
  • 현재 셀을 방문 처리한다.
• visited[r][c] = true; // 현재 셀을 방문 처리
• 탐색
  • 상하좌우로 인접한 셀을 탐색하여 그림의 크기를 증가시킨다.
• for (int i = 0; i < 4; i++) { // 상하좌우 방향으로 이동 int nr = r + dr[i]; // 다음 행 계산 int nc = c + dc[i]; // 다음 열 계산 if (nr < 0 || nc < 0 || nr >= n || nc >= m || visited[nr][nc]) continue; // 범위를 벗어나거나 이미 방문한 셀인 경우 건너뜀 if (paper[nr][nc] == 1) { // 인접 셀이 그림의 부분인 경우 visited[nr][nc] = true; // 인접 셀 방문 처리 dfs(nr, nc); // 재귀적으로 DFS 호출 max++; // 그림의 크기 증가 } }

5. 전체 코드

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

public class BOJ1926 {
    static int n, m, max; // 행과 열의 크기, 현재 최대 그림 크기
    static int[][] paper; // 그림 정보를 저장하는 2차원 배열
    static boolean[][] visited; // 방문 여부를 기록하는 2차원 배열
    static int[] dr = {-1, 1, 0, 0}; // 상하 방향 이동을 위한 행 변화량
    static int[] dc = {0, 0, -1, 1}; // 좌우 방향 이동을 위한 열 변화량

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 위한 BufferedReader 객체 생성
        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 cnt = 0; // 그림의 개수
        List<Integer> sizes = new ArrayList<>(); // 각 그림의 크기를 저장하는 리스트
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (paper[i][j] == 1 && !visited[i][j]) { // 그림이 있는 셀을 발견한 경우
                    max = 1; // 현재 그림의 크기를 1로 초기화
                    dfs(i, j); // DFS로 그림의 크기를 계산
                    sizes.add(max); // 그림의 크기를 리스트에 추가
                    cnt++; // 그림 개수 증가
                }
            }
        }

        // 결과 출력
        if (cnt == 0) {
            System.out.println(cnt + "\n" + 0); // 그림이 없는 경우
        } else {
            System.out.println(cnt + "\n" + Collections.max(sizes)); // 그림의 개수와 최대 크기 출력
        }
    }

    // DFS를 이용하여 그림의 크기를 계산하는 함수
    public static void dfs(int r, int c) {
        visited[r][c] = true; // 현재 셀을 방문 처리
        for (int i = 0; i < 4; i++) { // 상하좌우 방향으로 이동
            int nr = r + dr[i]; // 다음 행 계산
            int nc = c + dc[i]; // 다음 열 계산

            // 배열의 범위를 벗어나거나 이미 방문한 셀인 경우 건너뜀
            if (nr < 0 || nc < 0 || nr >= n || nc >= m || visited[nr][nc]) continue;

            // 인접 셀이 그림의 부분인 경우
            if (paper[nr][nc] == 1) {
                visited[nr][nc] = true; // 인접 셀 방문 처리
                dfs(nr, nc); // 재귀적으로 DFS 호출
                max++; // 그림의 크기 증가
            }
        }
    }
}