[白俊]2468安全区域
問題とI/O
質問へのアクセス
初めて問題に近づいたとき,全部で3段階に分けて問題を解いた.
bfsは
上記の3つのステップを領域の高さで繰り返し、計算した数字のうち、最大停止した数字がこの問題の答えです.
その後解答を提出したところ、解答は成功した(実は正しいとは思わなかった)
コードの長さはかなり長く、成功しましたが、メモリと時間の観点からは効率が低いと思います.
そのため、再考の結果、第3段階では安全区域を明記する必要はないと思います.なぜなら、未アクセス領域において、水の高さよりも高い領域を巡回すると考えられる場合、既存の1,2ステップを一度に実現することができるからである.
これに基づいて再実現し、メモリと時間を節約し、成功したプールを再実現しました.
インプリメンテーションコード
初めての試み
import java.util.*;
import java.io.*;
class Reg {
int x;
int y;
Reg(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static int N;
static int max = 0;
static Integer[][] reg;
static boolean[][] check;
static boolean[][] got;
static int[] dx = { 1, 0, -1, 0 };
static int[] dy = { 0, -1, 0, 1 };
static int solve() {
int count = 0;
for (int i = 0; i < max; i++) {
check = new boolean[N][N];
got = new boolean[N][N];
bfs(i);
count = find_max(count);
}
return count;
}
static void bfs(int i) {
Queue<Reg> q = new LinkedList<Reg>();
q.add(new Reg(0, 0));
while (!q.isEmpty()) {
Reg temp = q.remove();
for (int j = 0; j < 4; j++) {
int x = temp.x + dx[j];
int y = temp.y + dy[j];
if (x >= 0 && y >= 0 && x < N && y < N) {
if (!got[x][y]) {
if (reg[x][y] <= i) {
check[x][y] = true;
}
q.add(new Reg(x, y));
got[x][y] = true;
}
}
}
}
}
static int find_max(int count) {
int result = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!check[i][j]) {
check_true(i, j);
result++;
}
}
}
return Math.max(count, result);
}
static void check_true(int tx, int ty) {
Queue<Reg> q = new LinkedList<Reg>();
q.add(new Reg(tx, ty));
while (!q.isEmpty()) {
Reg temp = q.remove();
for (int j = 0; j < 4; j++) {
int x = temp.x + dx[j];
int y = temp.y + dy[j];
if (x >= 0 && y >= 0 && x < N && y < N) {
if (!check[x][y]) {
check[x][y] = true;
q.add(new Reg(x, y));
}
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
reg = new Integer[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int j = 0;
while (st.hasMoreTokens()) {
int temp = Integer.parseInt(st.nextToken());
if (temp > max)
max = temp;
reg[i][j] = temp;
j++;
}
}
System.out.println(solve());
}
}import java.util.*;
import java.io.*;
class Reg {
int x;
int y;
Reg(int x, int y) {
this.x = x;
this.y = y;
}
}
public class bj2468 {
static int N;
static Integer[][] reg;
static boolean[][] check;
static int[] dx = { 1, 0, -1, 0 };
static int[] dy = { 0, -1, 0, 1 };
static void dfs(int tx, int ty, int depth) {
Queue<Reg> q = new LinkedList<Reg>();
q.add(new Reg(tx, ty));
while (!q.isEmpty()) {
Reg temp = q.remove();
for (int i = 0; i < 4; i++) {
int x = temp.x + dx[i];
int y = temp.y + dy[i];
if (x >= 0 && y >= 0 && x < N && y < N) {
if (!check[x][y] && reg[x][y] > depth) {
q.add(new Reg(x, y));
check[x][y] = true;
}
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
reg = new Integer[N][N];
int max = 0;
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int j = 0;
while (st.hasMoreTokens()) {
int temp = Integer.parseInt(st.nextToken());
if (temp > max)
max = temp;
reg[i][j] = temp;
j++;
}
}
int result = 0;
for (int depth = 0; depth < max; depth++) {
check = new boolean[N][N];
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!check[i][j] && reg[i][j] > depth) {
dfs(i, j, depth);
count++;
}
}
}
result = Math.max(count, result);
}
System.out.println(result);
}
}Reference
この問題について([白俊]2468安全区域), 我々は、より多くの情報をここで見つけました https://velog.io/@choiish98/백준-2468-안전영역テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol