백준 1926, 그림 - DFS & BFS

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

1. 아이디어

• 2중 for문으로 도화지 [0][0] ~ [n-1][m-1] 확인
  => 해당 지점이 그림(1, true)이고 아직 방문 안한 경우, 해당 지점을 기준으로 탐색 (DFS / BFS) 수행
  
  

1) DFS

• 재귀함수
• 해당 지점을 기준으로 상하좌우 확인
• 상하좌우 각각에서 도화지 범위 안이고, 그림이고, 아직 방문 안한 경우, 탐색 확장해나감 (재귀 호출)

2) BFS

• Queue
• Queue가 empty 할 때까지 반복
  ① Queue에서 좌표를 하나 꺼냄
  ② 꺼낸 좌표를 기준으로 상하좌우 확인
  ③ 좌표의 상하좌우 각각에서 도화지 범위 안이고, 그림이고, 아직 방문 안한 경우, Queue에 추가

  다음 차례에 탐색할 좌표를 Queue에 추가하면서, 방문 처리 할 것

2. 자료구조

• boolean[][]: 도화지(그래프)
• boolean[][]: 방문 확인
• Queue<Integer>: BFS

3. 시간 복잡도

• DFS와 BFS의 시간 복잡도 = O(V + E) (V: vertex 개수, E: edge 개수)
  ① V (vertex 개수): n x m
  ② E (edge 개수): 4V (넉넉하게 한 vertex 에 연결된 vertex 상하좌우 4개로 생각)
  => 최대 O(V + E) = O(5V) = O(n x m x n) = O(5 x 500 x 500) = O(1,250,000) << 2억 (2초)

코드 ① - DFS 풀이

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

public class Main {
    static int n, m;                // n: 도화지 세로 크기, m: 도화지 가로 크기
    static boolean[][] paper;       // 가로 m, 세로 n 도화지
    static boolean[][] check;       // 방문 확인

    static int numberOfPicture = 0;     // 그림 개수
    static int maxArea = 0;             // 가장 넓은 그림의 넓이
    static int area = 0;                // 탐색한 그림의 넓이

    static int[] dy = { -1, 1, 0, 0 };      // 상하좌우
    static int[] dx = { 0, 0, -1, 1 };
    
    public static void dfs(int row, int col) {
        check[row][col] = true;
        area++;

        // 상하좌우 확인
        for (int i = 0; i < 4; i++) {
            int nextRow = row + dy[i];
            int nextCol = col + dx[i];

            // 1. 다음 지점이 도화지 범위 안이고
            if (0 <= nextRow && nextRow < n &&
                0 <= nextCol && nextCol < m) {
                // 2. 그림이고 아직 방문 안한 경우
                if (paper[nextRow][nextCol] && !check[nextRow][nextCol])
                    dfs(nextRow, nextCol);
            }
        }
    }

    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());
        
        check = new boolean[n][m];
        paper = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < m; j++) {
                int input = Integer.parseInt(st.nextToken());
                if (input == 1)
                    paper[i][j] = true;
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 해당 지점이 그림이고 아직 방문 안한 경우, 탐색 수행
                if (paper[i][j] && !check[i][j]) {
                    numberOfPicture++;
                    dfs(i, j);
                    // bfs(i, j);

                    maxArea = Math.max(maxArea, area);
                    area = 0;       // area 초기화
                }
            }
        }

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

코드 ② - BFS 풀이

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

class Coord {
    private int row;
    private int col;

    public Coord(int row, int col) {
        this.row = row;
        this.col = col;
    }
    public int getRow() { return row; }
    public int getCol() { return col; }
}

public class Main {
    static int n, m;                // n: 도화지 세로 크기, m: 도화지 가로 크기
    static boolean[][] paper;       // 가로 m, 세로 n 도화지
    static boolean[][] check;       // 방문 확인
    
    static int numberOfPicture = 0;     // 그림 개수
    static int maxArea = 0;             // 가장 넓은 그림의 넓이
    static int area = 0;                // 탐색한 그림의 넓이

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

    public static void bfs(int row, int col) {
        Queue<Coord> queue = new LinkedList<>();

        queue.add(new Coord(row, col));
        check[row][col] = true;
        area++;

        while (!queue.isEmpty()) {
            Coord c = queue.remove();

            // 상하좌우 확인
            for (int i = 0; i < 4; i++) {
                int nextRow = c.getRow() + dy[i];
                int nextCol = c.getCol() + dx[i];

                // 1. 다음 지점이 도화지 범위 안이고
                if (0 <= nextRow && nextRow < n &&
                    0 <= nextCol && nextCol < m) {
                    // 2. 그림이고 아직 방문 안한 경우
                    if (paper[nextRow][nextCol] && !check[nextRow][nextCol]) {
                        queue.add(new Coord(nextRow, nextCol));
                        check[nextRow][nextCol] = true;
                        area++;
                    }
                }
            }
        }
    }

    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());
        
        check = new boolean[n][m];
        paper = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < m; j++) {
                int input = Integer.parseInt(st.nextToken());
                if (input == 1)
                    paper[i][j] = true;
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 해당 지점이 그림이고 아직 방문 안한 경우, 탐색 수행
                if (paper[i][j] && !check[i][j]) {
                    numberOfPicture++;
                    bfs(i, j);
                    // dfs(i, j);

                    maxArea = Math.max(maxArea, area);
                    area = 0;       // area 초기화
                }
            }
        }

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