白駿2468号:安全区域
21467 ワード
問題の説明
方法
pseudocode
for(h는 1부터 가장 높은 지점의 숫자까지){
// 높이가 h 이하인 지역이 물에 잠깁니다.
for(i는 0부터 N까지){
for(j는 0부터 N까지){
BFS(i,j,h);
}
}
// 섬의 개수를 구합니다.
for(i는 0부터 N까지){
for(j는 0부터 N까지){
// 1001은 임의의 숫자입니다. 저는 물에 잠긴 지역을 1002로 표현했습니다.
// 섬을 구하기 위해서는 100(지역의 최대높이) < x <1002(물에 잠긴 걸 표현)를 만족하는 x로 BFS를 실행해야 합니다.
BFS(i,j,1001);
}
}
}
正解
import java.io.*;
import java.util.*;
class Main {
static int MaxHeight = 0;
static int[] dx = { 1, 0, -1, 0 };
static int[] dy = { 0, -1, 0, 1 };
static int N;
static int Answer = 1;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
int[][] board = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int val = sc.nextInt();
board[i][j] = val;
MaxHeight = Math.max(val, MaxHeight);
}
}
for (int h = 1; h <= MaxHeight; h++) {
int[][] CopyBoard = new int[N][N];
for (int i = 0; i < N; i++) {
CopyBoard[i] = board[i].clone();
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
BFS(i, j, h, CopyBoard);
}
}
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (CopyBoard[i][j] < 1002) {
cnt++;
BFS(i, j, 1001, CopyBoard);
}
}
}
Answer = Math.max(Answer, cnt);
}
System.out.println(Answer);
}
public static void BFS(int x, int y, int h, int[][] board) {
Queue<int[]> q = new LinkedList<int[]>();
int[] temp = { x, y };
q.add(temp);
while (!q.isEmpty()) {
int[] now = q.poll();
for (int d = 0; d < 4; d++) {
int nx = now[0] + dx[d];
int ny = now[1] + dy[d];
if (0 <= nx && nx < N && 0 <= ny && ny < N && board[nx][ny] <= h) {
int[] next = { nx, ny };
q.add(next);
board[nx][ny] = 1002;
}
}
}
}
}
Reference
この問題について(白駿2468号:安全区域), 我々は、より多くの情報をここで見つけました https://velog.io/@qwerty1434/백준-2468번-안전-지역テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol