백준 | 1926번. 그림 - DFS, BFS 모두 풀이

🟦 백준 1926번. 그림

문제

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

입력

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

출력

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

💚나의 풀이 1 - DFS 풀이

• 결과는 제대로 나왔었는데, 백준 채점 시 계속 런타임 에러가 떴다.
• 1) pnum[] 값으로 각 num번호 그림별 넓이를 카운팅하려고 했는데 인덱스 참조 범위를 넘어섰다는 식으로 에러가 났다.
• 2) ArrayList로 add처리했을 때도 마찬가지였다.
• 3) 일반 max 값으로 Math.max(max, count) 식으로 복귀된 count값만 세팅해주니 정상 작동하여 맞췄다.

package to_0613_1;

import java.util.Scanner;

/*1926번. 그림 - DFS 로 풀이 */
public class Main {
    static int N, M;
    static int[][] picture;
    static boolean[][] visited;

    //방향 -상하좌우
    static int[]dx = {0, 0, 1, -1};
    static int[]dy = {1, -1, 0, 0};

    //정답용
    static int num;//그림 넘버이자, 총개수가 누적될 변수 
    static int count;
    static int max = 0;

    //DFS
    static void DFS(int x, int y) {
        visited[x][y] = true;//방문 처리 
        //각 개수 너비 탐색 
        count++;

        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx<0 || ny <0 || nx >=N || ny >= M) continue;
            if(picture[nx][ny] == 0 || visited[nx][ny] == true) continue;

            //그 외에 대해서는 깊이 DFS 탐색 
            DFS(nx, ny);
        }
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Scanner kb =new Scanner(System.in);

        N = kb.nextInt();
        M = kb.nextInt();

        picture = new int[N][M];
        visited = new boolean[N][M];

        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                picture[i][j] = kb.nextInt();
            }
        }
        //호출
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                //색칠된 그림이면서 방문 전인 좌표에 대하여 차례로 전진 
                if(picture[i][j]==1 && !visited[i][j]) {
                    num++;//번호 ++처리 == DFS 호출 횟수가 총 그림개수가 됨
                    DFS(i, j);
                    //여기서 복귀된 count를 Arraylist에 담아?
                    max = Math.max(max, count);

                    count= 0; //여기서 다 시 0 세팅
                }

            }
        }
        System.out.println(num);
        System.out.println(max);
    }
}

💚나의 풀이 - BFS 풀이

• BFS는 각 뿌리 호출 시, 해당 함수 내에서 Queue에 다음 인접 정점을 담으면서 인근 너비 우선 탐색을 시도할 거다.
• 인근의 BFS로 끝까지 가다가 큐 내부가 빈 상태 (즉, 인접 정점 없으면) 복귀하여 다시 main으로 돌아오는데, 이때의 count값을 기존의 max와 비교하며 가장 큰 값을 max에 담도록 하고, 마찬가지로 BFS 호출 횟수가 총 그림의 덩어리 개수가 되므로 그렇게 답을 출력했다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/*1926번. 그림 - BFS 풀이 */
public class Main {
    static int N, M;
    static int[][] picture;
    static boolean[][] visited;

    //상하좌우
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    //정답용
    static int num;
    static int cnt;

    //BFS
    static void BFS(int x, int y) {
        Queue<int[]> Q= new LinkedList<>();

        cnt = 1;
        visited[x][y] = true;
        Q.add(new int[] {x, y});

        while(!Q.isEmpty()) {
            int[] cur = Q.poll();

            for(int i=0; i<4; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];

                if(nx <0 || ny <0 || nx >=N || ny>=M) continue;
                if(picture[nx][ny] == 0 || visited[nx][ny]==true) continue;

                //BFS 정상 처리
                visited[nx][ny] = true;
                Q.add(new int[] {nx, ny});
                cnt++; //너비++
            }
        }
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Scanner kb = new Scanner(System.in);
        N = kb.nextInt();
        M = kb.nextInt();

        picture = new int[N][M];
        visited = new boolean[N][M];

        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                picture[i][j] = kb.nextInt();
            }
        }
        int max = 0;

        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(picture[i][j] == 1 && !visited[i][j]) {
                    num++;//호출 횟수 == 어쨋든 덩어리 총 수 
                    BFS(i,j);
                    max = Math.max(max, cnt);
                }
            }
        }

        System.out.println(num + "\n" + max);
    }
}