[백준 1926] Java - 그림

 

그림

 

 

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

 

 

 

 

 

1)  문제

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와 가장 넓은 그림의 넓이를 출력하여라.
그림은 1로 연결된 영역이고, 가로나 세로로만 연결된 것을 연결된 것이라 한다.
그림의 넓이는 1의 개수이다.

입력: 세로 크기 n (1 ≤ n ≤ 500), 가로 크기 m (1 ≤ m ≤ 500)
이후 n줄에 걸쳐 0과 1로 이루어진 도화지 정보 제공
출력: 그림의 개수와 가장 넓은 그림의 넓이 (없으면 0)

 

 

2)  예시

입력	출력
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

 

 

3)  풀이

 

1. 아이디어
2중 for문으로 모든 좌표 순회 → 값이 1이면서 방문하지 않았으면 BFS 실행
BFS 돌 때마다 그림 개수 +1, 넓이를 계산해 최대값 갱신

 

 

 

2. 시간복잡도
BFS는 O(V + E)이며,
V: 최대 500*500, E: 각 정점당 최대 4방향 연결이므로 E = 4V
최대 O(5 * 250,000) = 1,250,000 → 충분히 가능

(코딩테스트는 2초간 2억번정도는 허용된 연산량)

 

 

 

3. 자료구조

• 그래프 지도: int[][]
• 방문 확인: boolean[][]
• 탐색용 큐: Queue

 

 

 

4)  코드

import java.util.*;

public class Main {
    static int n, m;
    static int[][] graph;
    static boolean[][] visited;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        graph = new int[n][m];
        visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                graph[i][j] = sc.nextInt();
            }
        }

        int count = 0;
        int maxArea = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && graph[i][j] == 1) {
                    count++;
                    maxArea = Math.max(maxArea, bfs(i, j));
                }
            }
        }

        System.out.println(count);
        System.out.println(maxArea);
    }

    static int bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;
        int area = 1;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int cx = cur[0];
            int cy = cur[1];

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

                if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                    if (!visited[nx][ny] && graph[nx][ny] == 1) {
                        visited[nx][ny] = true;
                        queue.offer(new int[]{nx, ny});
                        area++;
                    }
                }
            }
        }
        return area;
    }
}

 

 

 

주석으로 설명

import java.util.*;
//자바 유틸을 가져와 queue, Scanner를 사용할 수 있게함

public class Main {
// 자바는 클래스단위로 실행되니, Main 클래스 정의
// 아래 변수들은 다른 메소드에서 사용할 수 있게 static으로 선언
    static int m, n;
  	// 도화지의 가로 m, 세로n
    static int[][] graph;
    // 도화지의 전체상태를 저장할 이차원배열 (0: 빈칸, 1: 그림)
    static boolean[][] visited;
    // 이미 방문한 칸인지를 저장하는 배열, x,y좌표가 들어가게해서 이차원배열
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
	// 하상우좌로 이동시키기위한 배열을 선언

    public static void main(String[] args) {
	// 자바의 시작점인 메인메서드
        Scanner sc = new Scanner(System.in);
        // 입력을 위한 스캐너 객체 생성
        n = sc.nextInt();
        m = sc.nextInt();
        // 가로m과 세로n을 입력받음
        graph = new int[n][m];
        visited = new boolean[n][m];
        // 도화지 및 방문여부 상태를 초기화

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                graph[i][j] = sc.nextInt();
            }
        }
        // 이중반복문을 이용하여 도화지의 상태(0또는1)를 저장함

        int count = 0;
        int maxArea = 0;
		// 그림의 개수와 가장 넓은 그림의 넓이를 선언
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
            // 이중반복문으로 전체 도화지를 순회
                if (!visited[i][j] && graph[i][j] == 1) {
                // 방문하지 않은 그림이 있는 곳이라면 (BFS 조건)
                    count++;
                // 그림의 개수를 1 증가시킴
                    maxArea = Math.max(maxArea, bfs(i, j));
                // bfs 메소드로 현재 그림의 넓이를 구하고 지금까지 넓이와 비교하여 갱신
                }
            }
        }

        System.out.println(count);
        System.out.println(maxArea);
        // count와 maxArea 출력
    }

    static int bfs(int x, int y) {
    //BFS 탐색을 위한 메소드
        Queue<int[]> queue = new LinkedList<>();
        //BFS를 위한 Queue선언, int[]은 x,y좌표 배열
        queue.offer(new int[]{x, y});
        visited[x][y] = true;
        // 시작좌표를 큐에 넣고, 방문한 것으로 처리함
        int area = 1;
        // 현재 그림의 넓이를 1로 초기화

        while (!queue.isEmpty()) {
        // queue가 빌때까지 계속 반복함
            int[] cur = queue.poll();
            int cx = cur[0];
            int cy = cur[1];
            // 큐에서 현재 좌표를 꺼냄

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
			// 상하좌우 이동할 새좌표를 계산
                if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                // 배열의 범위를 벗어나지않은경우(즉, 길이가 음수가 아니고 가로세로안)
                    if (!visited[nx][ny] && graph[nx][ny] == 1) {
                    // 방문하지 않았고, 그림이 있는 경우
                        visited[nx][ny] = true;
                        queue.offer(new int[]{nx, ny});
                        area++;
                        // 큐에 넣고 방문처리하고, 넓이를 1 증가시킴
                    }
                }
            }
        }
        return area;
        //그림의 넓이를 반환함
    }
}

 

 

 

 

5)  리뷰

 

BFS 문제를 처음 접하는데 기본을 배우기 좋은 문제였다.