[BOJ] 2468. 安全エリア★☆

質問する

防災庁は大雨の雨季に備えて、次のようなことを計画しています.まず、ある地域の高度な情報を理解します.そして、この地域が大雨の時に最大でどれだけの浸水しない安全区域を形成できるかを調べます.このとき,問題を単純化するために,雨季の雨量が一定の高さ以下のすべての場所が水没すると仮定した.
一部の領域の高さ情報は、行と列のサイズがそれぞれNの2次元配列の形で与えられ、配列内の各要素は、その点の高さを表す自然数である.例えば、以下はN=5の領域の高さ情報である.

現在、上のような地域では大雨が降っており、4より低いところはすべて水没しています.この場合、水没点は以下のようにグレーで表される.

水没しない安全区域とは、水没しない場所が上、下、右または左に隣接し、その大きさが最も大きい区域を指す.上記の場合、水没しない安全区域は5つある(死点付着のみとは思えない2つの地点が隣接している).
また、上記の地域で大雨が降って高さ6以下のすべての場所が水没した場合、水没しない安全区域は、下図のように4つ確認できます.

このように雨季によって降雨量が異なり、水没しない安全区域の個数も異なる.前例のように雨量によってすべての状況を調べた結果,水没しない安全区域の個数のうち最大は5であった.
地域の高さ情報を取得する場合は、雨季に浸水しない安全な地域の最大数を計算するプログラムを作成します.

入力

1行目は、ある領域の2次元配列を表す行数と列数Nを入力する.Nは2以上100以下の整数である.2行目からN行目まで、2次元配列の1行目からN行目までの高さ情報を順次入力します.各行において、各行の第1列から第N列までのN個の高さ情報を表す自然数がスペースを隔てて入力される.高さは1以上100以下の整数です.

しゅつりょく

第1行は雨季に浸水しない安全区域の最大数を出力する.

入力例1

5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

サンプル出力1

5

入力例2

7
9 9 9 9 9 9 9
9 2 1 2 1 2 9
9 1 8 7 8 1 9
9 2 7 9 7 2 9
9 1 8 7 8 1 9
9 2 1 2 1 2 9
9 9 9 9 9 9 9

サンプル出力2

6

に答える

コード#コード#

① bfs

import java.io.*;
import java.util.*;


public class Main_bj_2468_안전영역_bfs {

	static int N;
	static int[][] area;
	static boolean[][] visited;
	static final int[] di = {-1, 0, 1, 0};
	static final int[] dj = {0, 1, 0, -1};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		area = new int[N][N];
		
		int max=0;
		StringTokenizer st;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				area[i][j] = Integer.parseInt(st.nextToken());
				if(area[i][j] > max) max = area[i][j];
			}
		}

		int ansMax  = 1;
		for (int rain=1; rain<max; rain++) {
			visited = new boolean[N][N];

			int cnt=0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (area[i][j]>rain && !visited[i][j]) {
						cnt++;
						bfs(i, j, rain);
					}
				}
			}

			ansMax = Math.max(ansMax, cnt);
		}

		System.out.println(ansMax);
		br.close();
	}
	
	static void bfs(int i, int j, int rain) {
		Queue<int[]> que = new ArrayDeque<int[]>();
		que.offer(new int[]{i, j});
		visited[i][j] = true;
		
		while(!que.isEmpty()) {
			int[] cur = que.poll();
			
			for(int k=0; k<4; k++) {
				int ni = cur[0]+di[k];
				int nj = cur[1]+dj[k];
				
				if(ni<0 || ni>=N || nj<0 || nj>=N) continue;
				if(area[ni][nj]<=rain || visited[ni][nj]==true) continue;
				visited[ni][nj] = true;
				que.offer(new int[] {ni, nj});
			}
		}
		
	}


}

② dfs

import java.io.*;
import java.util.*;

public class Main_bj_2468_안전영역_dfs {

	static int N;
	static int[][] area;
	static boolean[][] visited;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		area = new int[N][N];
		
		int max=0;
		StringTokenizer st;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				area[i][j] = Integer.parseInt(st.nextToken());
				if(area[i][j] > max) max = area[i][j];
			}
		}

		int ansMax  = 1;
		for (int rain=1; rain<max; rain++) {
			visited = new boolean[N][N];

			int cnt=0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (area[i][j]>rain && !visited[i][j]) {
						cnt++;
						dfs(i, j, rain);
					}
				}
			}

			ansMax = Math.max(ansMax, cnt);
		}

		System.out.println(ansMax);
		br.close();
	}
	
	static void dfs(int i, int j, int rain) {
		if(i<0 || i>=N || j<0 || j>=N ) {
			return;
		}
		if(area[i][j] <= rain || visited[i][j]==true) return;
		
		visited[i][j] = true;
		
		dfs(i-1, j, rain);
		dfs(i, j+1, rain);
		dfs(i+1, j, rain);
		dfs(i, j-1, rain);
		
	}


}

.java (bfs)
.java (dfs)