Java

[백준 2468] 안전 영역 (JAVA)

iheeeee6-6 2023. 4. 19. 12:36
728x90

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

 

2468번: 안전 영역

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는

www.acmicpc.net

 

처음에 문제를 잘못 이해해서 힘들었다..

안전한 영역의 뭉탱이를 구하는 문제로, 

비가 0 ~ 최대값까지 내렸을때의 안전 영역 최대 갯수를 구한다!

(필자는 최소값도 구하여 확인했었으나, 비가 안왔을때의 가정도 있다는 거!!!!!!)

인접한 구역에 대한 방문 처리를 한 후, 1을 리턴한다. (뭉탱이이기에 1 리턴)

그렇게 count를 계산하여 최대 갯수를 구한다~

 

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

public class Main {

	static int[] dx= {1,-1,0,0};
	static int[] dy= {0,0,1,-1};
	static boolean[][] visited;
	static int[][] arr;
	static int n;
	static int max = Integer.MIN_VALUE;
	static int result=0;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		 n= Integer.parseInt(br.readLine());
		arr = new int[n][n];
		StringTokenizer st;
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<n;j++) {
				arr[i][j]= Integer.parseInt(st.nextToken());
				max =Math.max(arr[i][j],max);
			}
		}
		for(int i=0;i<=max;i++) {
			visited=new boolean[n][n];
			int count=0;
			for(int j=0;j<n;j++) {
				for(int z=0;z<n;z++) {
					if(!visited[j][z]&&arr[j][z]>i)
						count+= dfs(j,z,i);
				}
			}
			 result=Math.max(result, count);
		}
		
		System.out.println(result);
	}

	static public int dfs(int x,int y,int size) {
		visited[x][y]=true;	
		for(int i=0;i<4;i++) {
			int xx = x+dx[i];
			int yy= y+dy[i];
			if(xx<0||yy<0||xx>=n||yy>=n||visited[xx][yy]) continue;
			if(arr[xx][yy]>size)dfs(xx,yy,size);
		}
		return 1;
	}
}