[백준] 2468 안전 영역 - BFS(넓이우선탐색) JAVA

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

코드설명

BFS(넓이우선탐색) 를 활용합니다.

 

장마철에 오는 비의 양을 0부터 ~100까지 모두 실행해서 각각의 안전거리를 구하면 되는 문제입니다.

코드

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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, T;
	static int answer = 0;
	static int[][] matrix = new int[101][101];
	static boolean[][] visited = new boolean[101][101];
	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());
		for(int i=0;i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int height = 0; height < 100; height++) {
			visited = new boolean[101][101];
			int safePlace = 0;
			for(int i=0;i<N; i++) {
				for(int j=0;j<N;j++) {
					if(matrix[i][j] - height > 0 && visited[i][j] == false) {
						safePlace+= 1;
						BFS(i, j, height);
					}
				}
			}
			
			answer = Math.max(answer, safePlace);
		}
		System.out.println(answer);
	}
	
	static void BFS(int sr, int sc, int height) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {sr, sc});
		visited[sr][sc] = true;
		
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			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 >= N) continue;
				if(visited[nr][nc] == true) continue;
				if(matrix[nr][nc] - height <= 0) continue;
				q.offer(new int[] {nr, nc});
				visited[nr][nc] = true;
			}
		}
	}
	
}