백준 1926번 그림(JAVA) - BFS

백준 1926번 

 

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

1926번: 그림

 

 

 

문제설명

도화지의 크기 n,m을 입력받고 연결된 그림중 가장큰수, 그림의 개수를 구하는 문제 ( 1로 연결된것은 한개의 그림, 가로 세로만 연결된 것으로 가정)

 

 

접근

BFS로 접근

 

 

코드

package boj;


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

public class boj_1926 {

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int[][] map;
    static boolean[][] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(tk.nextToken());
        int m = Integer.parseInt(tk.nextToken());
        Queue<int[]> q = new LinkedList<>();

        map = new int [n][m];
        visit = new boolean[n][m];

        for(int i=0;i<n;i++){
            tk = new StringTokenizer(br.readLine());
            for(int j=0;j<m;j++){
                map[i][j] = Integer.parseInt(tk.nextToken());
            }
        }
        int max = 0;    //그림의 최댓값
        int num = 0;    //그림의수

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(map[i][j] == 0 || visit[i][j]) continue;
                num++;
                visit[i][j] = true;
                q.offer(new int[] {i,j});
                int area = 0 ;
                while(!q.isEmpty()){
                    area++;
                    int[] temp = q.poll();
                    int x = temp[0];
                    int y = temp[1];

                    for(int dir = 0;dir < 4; dir++){
                        int nx = x + dx[dir];
                        int ny = y + dy[dir];
                        if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                        if(visit[nx][ny] || map[nx][ny] !=1) continue;
                        visit[nx][ny] = true;
                        q.offer(new int[]{nx,ny});
                    }
                }
                max = Math.max(max,area);
            }
        }
        System.out.println(num);
        System.out.println(max);
    }
}

 

풀이

1. 상,하,좌,우 네방향의 좌표를 가진 dx,dy선언

2. n,m을 입력받고 map 2차원배열, visit (방문 여부)을 생성해준다.

3. 한 점에서 출발하는 BFS가 아니라 출발점이 여러개가 될 수 있어서 이중포문으로 돌면서 탐색

4. 하나의 포문이 시작되는 순간 그림의 개수는 한개가 증가 (num) 그 후에 해당 좌표 (0,0)을 방문여부 체크 해주고 q에 넣는다. 그후 q가 비어있지 않을동안 while돌며 탐색 

4-1. 제일먼저 들어간 큐의 값을 꺼내고 해당 x,y좌표를 가져온다.

4-2. 네방향(dx,dy)을 다 돌며 방문했는지, 1(그림)인지 체크후 해당 좌표 true로 변경후, q에 삽입

4-3. 제일 큰 그림의 크기도 구해야하니까 for문이 끝나기전 max값이랑 비교해 갱신