Java 1926 그림

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

1926번: 그림

 

 

bfs로 풀 수 있는 문제이다. 

도화지를 입력 받은 뒤 원소의 값이 1이거나, 아직 방문하지 않은 곳이라면 하나의 그림이기 때문에 cnt 변수에 1을 더해준다.

그리고 bfs함수를 실행시켜 상,하,좌,우에 인접한 1의 개수만큼 큐에 추가하며 탐색을 진행해준 뒤 max의 값을 업데이트 해주어 문제에서 제시한 값을 도출할 수 있었다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {

    static int n,m;
    static int[][] canvas;
    static boolean[][] visited;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static Queue<Node> q = new LinkedList<>();
    static int max = 0;
    static int cnt = 0;

    static class Node {
        int x;
        int y;

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

    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());

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

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(canvas[i][j] == 1 && !visited[i][j]){
                    bfs(i, j);
                    cnt++;
                }
            }
        }

        System.out.println(cnt);
        System.out.println(max);


    }
    static void bfs(int x, int y){
        int tmp = 1;
        q.add(new Node(x,y));
        visited[x][y] = true;

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

            for(int i = 0; i < 4; i++){
                int nx = poll.x + dx[i];
                int ny = poll.y + dy[i];

                if(nx < 0 || ny < 0 || nx >= n || ny >= m){
                    continue;
                }
                if(canvas[nx][ny] == 1 && !visited[nx][ny]){
                    visited[nx][ny] = true;
                    q.add(new Node(nx, ny));
                    tmp++;
                }
            }
        }
        max = Math.max(max, tmp);
    }
}