[BOJ]1926번 그림

그림 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

38662

16860

11684

42.223%

문제

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

입력

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

출력

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

 

 

---

📝풀이

너도 할 수 있다!

간단한 DFS/BFS 문제

 

저는 DFS로 풀었습니다.

import java.util.*;

public class Main {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static boolean[][] visited;
    static int N,M;
    static int start, end;
    static int max = 0;; 
    static int count = 0;

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    //그래프 초기화
    public static void init(int N,int M){
        visited = new boolean[N][M];
        for(int i = 0; i<N; i++){
            graph.add(new ArrayList<Integer>());
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        init(N,M);
        for(int i = 0; i< N;i++){
            for(int j = 0; j<M;j++){
                graph.get(i).add(sc.nextInt());
            }
        }
        
        for(int i = 0; i< N;i++){
            for(int j = 0; j<M;j++){
                if(!visited[i][j]&&graph.get(i).get(j) == 1){
                    max = Math.max(dfs(i,j),max);
                    count++;
                }
            }
        }
        System.out.println(count +"\n"+max);
    }
    
    public static int dfs(int x, int y){
        visited[x][y] = true;
        int power = 1;

        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            if (isValid(nx, ny) &&!visited[nx][ny] && graph.get(nx).get(ny) == 1) {
                power += dfs(nx, ny);
            }
        }
        return power;
    }
    
        // 배열 범위 체크
    public static boolean isValid(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }
}