[백준] 1926. 그림

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

1926번: 그림

bfs 문제를 몇 달만에 풀어서 다 까먹었을까봐 걱정했는데 아주 쉬운 문제라서 그런지 잘 풀었다! 오랜만에 bfs를 푸는 만큼 쉬운 문제더라도 꼼꼼히 보자. 

 

bfs와 dfs 문제의 시간 복잡도는 O(V + E)이다. 이때 V는 노드의 개수, E는 간선의 개수이다. 

 

주의해야 할 점은 다음과 같다.

• 방문 후에는 방문 처리를 해주어야 한다.
• 따라서 그림이면서 방문하지 않았을 경우에만 bfs를 시작하고, 이때 그림의 개수를 +1 시켜준다. 이것이 한 덩이 그림의 시작점이다.
• bfs를 진행할 때는 큐를 사용하여 사방면을 탐색해준다.
  • 이때 이미 방문했거나 그래프 범위를 넘어가면 pass한다.
  • 그렇지 않으면 또 큐에 넣어주고 해당 그림의 넓이를 +1 시켜준다.

import java.io.BufferedReader;
import java.io.IOException;

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

// 시간복잡도: O(V + E)
// = O(n * m + 4V)
// = 250,000 + 4 * 250,000 = 1,250,000
public class Main {

    static int n; // 세로
    static int m; // 가로
    static int[][] map;
    static boolean[][] visited;
    static int count = 0; // 그림의 개수
    static int maxArea = 0; // 그림 중 가장 큰 것의 넓이
    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 = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = 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++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 그림이면서 아직 방문하지 않은 부분 -> 탐색 시작하기
                if (map[i][j] == 1 && !visited[i][j]) {
                    count++;
                    bfs(i, j);
                }
            }
        }

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

    private static void bfs(int y, int x) {
        int area = 0;
        Queue<Pair> que = new LinkedList<>();

        que.offer(new Pair(x, y));
        visited[y][x] = true;
        area++;

        while (!que.isEmpty()) {
            Pair p = que.poll();

            // 사방 탐색
            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];

                if (nx < 0 || nx >= m || ny < 0 || ny >= n || visited[ny][nx]) {
                    continue;
                }

                if (map[ny][nx] == 1) {
                    que.offer(new Pair(nx, ny));
                    visited[ny][nx] = true;
                    area++;
                }
            }
        }
        maxArea = Math.max(maxArea, area);
    }

    static class Pair {
        int x;
        int y;
        
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}