<Algorithm> 41. 2468번 안전영역

1. 2468번 안전영역

• 기본 DFS 문제, 비가 오는 모든 경우를 판단하고 모든 영역이 잠기지 않을때까지의 안전영역 중 가장 많은 영역을 출력

• 주의할점은 비가 오지 않는 경우도 포함 해야한다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class Main {     static boolean[][] visited;     static int count = 0;     static int max = 0;     public static void main(String[] args) throws IOException {         BufferedReader br =new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());         int N = Integer.parseInt(st.nextToken());         int[][] arr = new int[N][N];         visited = new boolean[N][N];                  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());             }         }                  for(int w = 0 ; w <= 100; w++) {// 비의 높이             for(int i = 0; i < N ; i++) {                 for(int j = 0; j < N ; j++) {                     if(!visited[i][j] && arr[i][j] > w) {// 잠기지 않는경우                         dfs(arr, N, i, j, w); // 영역 표시                         count++; // 안전영역의 개수                     }                 }             }             if(count == 0) { // 다 잠길 경우                 break;             }else {                 if(max < count) {                     max = count;                 }                     count = 0;                     visited = new boolean[N][N];             }         }                 System.out.println(max);     }          public static void dfs(int[][] arr, int N, int x, int y, int w) {                  int dx[] = {0, 0, 1, -1};         int dy[] = {1, -1, 0, 0};                  visited[x][y] = true;                  for(int i = 0; i < 4 ; i++) {             int nx = x + dx[i];             int ny = y + dy[i];                          if(nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[nx][ny] && arr[nx][ny] > w) {                 dfs(arr, N, nx, ny, w);             }             }     } }   Colored by Color Scripter

cs