[백준OJ] 1926번 그림

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

1926번: 그림

---

 

풀이

가장 기본적인 BFS문제이다. 그림을 만나면 해당 그림에 대한 BFS 탐색을 실시하며 넓이를 구해주고, 최대 넓이를 갱신해주면 된다.

 

시간복잡도

최악으로 모든 원소를 탐색하기 때문에 O(NM)이 된다.

 

코드

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

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

    public static boolean isIn(int[][] maze,int x,int y){
        return 0<=x && x<maze.length &&0<=y && y<maze[x].length;
    }
    //넓이를 반환
    public static int bfs(int[][] maze,boolean[][] visited,int x,int y){
        Queue<Node> q = new LinkedList<>();
        int[][] mv = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        int area = 1;
        q.offer(new Node(x,y));
        visited[x][y]=true;

        while(!q.isEmpty()){
            Node node = q.poll();

            for(int i=0;i<4;i++){
                int nx = node.x+mv[i][0];
                int ny = node.y+mv[i][1];

                if(isIn(maze,nx,ny) && !visited[nx][ny] && maze[nx][ny]==1){
                    q.offer(new Node(nx,ny));
                    visited[nx][ny]=true;
                    area++;
                }
            }
        }
        return area;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.valueOf(st.nextToken());
        int m = Integer.valueOf(st.nextToken());

        int maze[][] = new int[n][m];
        boolean[][] visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                maze[i][j] = Integer.valueOf(st.nextToken());
            }
        }

        int count = 0;
        int maxArea = 0;

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