[백준][Java] 1926번 : 그림

[문제 링크]

https://www.acmicpc.net/problem/1926

---

문제 설명

n × m 크기의 도화지에 있는 그림의 개수와 그림의 넓이가 가장 큰 것을 구한다.

0은 색칠이 안된 부분, 1은 색칠이 된 부분이고, 1로 연결된 것을 그림 이라고 한다.

 

 

 

 

 

 

문제 풀이

(1) DFS 사용

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

public class Main {

    static int[][] array;
    static int n, m;
    static int area = 0, cnt = 0, maxArea = 0;
    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;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());   //도화지 세로
        m = Integer.parseInt(st.nextToken());   //도화지 가로

        array = 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++) {
                array[i][j] = Integer.parseInt(st.nextToken());
            }
        }


        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(!visited[i][j] && array[i][j] == 1) {
                    cnt++;  //그림 개수 증가
                    dfs(i, j);
                    maxArea = Math.max(maxArea, area);  //그림의 최대 넓이 구하기
                    area = 0;   //다음 그림의 넓이를 구하기 위해 초기화
                }
            }
        }
        System.out.print(cnt + " \n" + maxArea);
    }

    //DFS 실행
    public static void dfs(int x, int y) {
        visited[x][y] = true;   //방문처리
        area++; //넓이 증가

        //상하좌우로 돌면서 아직 방문하지 않았고, 1인 부분을 탐색해서 재귀호출
        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(!visited[nx][ny] && array[nx][ny] == 1) {
                dfs(nx, ny);
            }
        }
    }
}

 

 

 

 

(2) BFS 사용

 

전체코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int[][] array;
    static int n, m;
    static int area = 0, cnt = 0, maxArea = 0;
    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;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());   //도화지 세로
        m = Integer.parseInt(st.nextToken());   //도화지 가로

        array = 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++) {
                array[i][j] = Integer.parseInt(st.nextToken());

            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(!visited[i][j] && array[i][j] == 1) {
                    cnt++;  //그림 개수 증가
                    bfs(i, j);
                    maxArea = Math.max(maxArea, area);  //그림의 최대 넓이 구하기
                    area = 0;   //다음 그림의 넓이를 구하기 위해 초기화
                }
            }
        }
        System.out.print(cnt + " \n" + maxArea);
    }

    //BFS 실행
    public static void bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x, y});   //시작 노드 삽입
        visited[x][y] = true;   //시작 노드 방문처리
        area++; //넓이 증가


        //큐가 빌 때까지 상하좌우를 돌면서 아직 방문하지 않았고, 1인 부분을 탐색해서 큐에 삽입
        while (!q.isEmpty()) {
            int[] poll = q.poll();
            x = poll[0];
            y = poll[1];

            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 (!visited[nx][ny] && array[nx][ny] == 1) {
                    visited[nx][ny] = true;
                    area++;
                    q.offer(new int[]{nx, ny});
                }
            }
        }
    }
}

 

 

 

 

✔️ 체크

어려운 문제는 아니었지만, 그림이 하나도 없는 경우 0 0 으로 출력해야하는데 0 만 출력하는 것으로 잘못 이해해서 조금 헤맸다.