[백준] 1926 그림 - BFS(너비우선탐색) JAVA

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

코드설명

 BFS(너비우선탐색)를 활용합니다.

 

각 그림을 만날떄마다 BFS를 실행하고, BFS내에서 그림을 마주했다면 해당 위치를 0 으로 바꾸어서 이후에 이미 방문한 그림공간은 다시 방문하지 않도록 합니다.

코드

package Main;
 
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 int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D;
	static int answer = 0;
	static int[][] matrix = new int[501][501];
	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());
		for(int i=0;i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int pictureCnt = 0;
		for(int i=0;i<N; i++) {
			for(int j=0; j<M; j++) {
				if(matrix[i][j] == 1) {
					pictureCnt += 1;
					answer = Math.max(answer, BFS(i, j));
				}
			}
		}
		System.out.println(pictureCnt);
		System.out.println(answer);
	}
	static int BFS(int sr, int sc) {
		Queue<int[]> q = new LinkedList<>();
		int retCnt = 0;
		q.offer(new int[] {sr, sc});
		matrix[sr][sc] = 0;
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			
			retCnt += 1;
			for(int[] dir : new int[][] { {0, 1}, {0, -1}, {-1, 0}, {1, 0} }) {
				int nr = temp[0] + dir[0];
				int nc = temp[1] + dir[1];
				
				if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
				if(matrix[nr][nc] == 0) continue;
				matrix[nr][nc] = 0;
				q.offer(new int[] {nr, nc});
			}
		}
		return retCnt;
		
	}
 
}