[DFS/BFS] 백준 1926번 그림(Java)

1926번: 그림

 

📚 문제

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

예제 입력	예제 출력
6 5 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1	4 9

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

 

📝 문제 해결

1인 영역(색칠된 부분)을 기준으로 상하좌우를 탐색하여 총 탐색 횟수(그림의 개수)와 최대 탐색 길이(그림의 넓이)를 출력하는 문제로

 

시작 지점에서 상하좌우를 살펴본 뒤 

if(x>=0 && x<n && y>=0 && y<m)	// 해당 좌표가 범위를 벗어나지 않고
if(map[nx][ny]==1)		// 색칠이 되있다면

해당 영역을 0으로 바꾸고 count(그림의 넓이)를 +1 해준다.

 

위의 과정을 반복하면서 탐색이 끝날 때마다 count를 List에 담아준다.

그림의 개수 : List 크기
가장 넓은 그림의 넓이 : List 정렬 후 마지막 인덱스 값

 

💻 코드

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class No1926 {
    static int n, m, count;
    static int[][] map;

    public static boolean dfs(int x, int y){
        if(x<0 || x>=n || y<0 || y>=m) return false;
        if(map[x][y] == 1){
            map[x][y] = 0;
            count += 1;

            dfs(x-1, y);
            dfs(x+1, y);
            dfs(x, y-1);
            dfs(x, y+1);
            return true;
        }
        return false;
    }

    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());

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

        List<Integer> arr = new ArrayList<>();
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                count = 0;
                if(dfs(i,j)){
                    arr.add(count);
                }
            }
        }

        Collections.sort(arr);
        System.out.println(arr.size());
        System.out.println(arr.size() == 0 ? 0 : arr.get(arr.size() - 1));
    }
}