π [λ°±μ€μκ³ λ¦¬μ¦ νμ΄] Q.2468 μμ μμ λ¬Έμ νμ΄
π λ¬Έμ
https://www.acmicpc.net/problem/2468
π μ κ·Όλ²
Q.2468 μμ μμ λ¬Έμ νμ΄μ λλ€.
μ λ ₯μΌλ‘ μ£Όμ΄μ§λ n*n λ§νΌμ μμμ
κ°κ°μ μμ λμ΄κ° μ£Όμ΄μ§λλ€.
λΉκ° λ΄λ¦΄ λ λΉμ μ κΈ°μ§ μλ μμ μμμ μ΅λ κ°μλ₯Ό ꡬνλ λ¬Έμ μ λλ€.
λΉμ μμ λ°λΌ μμ μμμ κ°μκ° λ€λ₯΄λ―λ‘ μ΅λ λΉμ μκΉμ§μ
λͺ¨λ κ²½μ°μ μλ₯Ό μ΄ν΄λ΄μΌν©λλ€.
κ°μ°λμ 0λΆν° λͺ¨λ μ κΈ°λ μμμ μ΅λ λμ΄κΉμ§ κ°λ₯ν©λλ€.
κ° κ°μ°λμ λ°λΌμ
bfs νμμ ν΅ν΄ κ°μ°λλ³΄λ€ λμ μμμ μΈμ ν μ§μ (κ·Έλν) κ°―μλ₯Ό ꡬνλ©΄ λ©λλ€.
λν μ΅λ κ°μλ₯Ό ꡬν΄μΌ νλ―λ‘
κ° κ°μ°λμ λ°λ₯Έ μ κΈ°μ§ μλ μμ μμμ κ°μλ₯Ό λΉκ΅ν΄ μ΅λκ°μ ꡬνλ©΄ λ©λλ€.
π» μ½λ
package problem.bfsdfs;
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
public class Main_2468 {
static int n;
static boolean[][] visited;
static int[][] area;
static int moveX[] = {0, 0, -1, 1};
static int moveY[] = {-1, 1, 0, 0};
static int max = 0;
static int maxArea = 0;
static int count =0;
public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
input();
for (int h = 0; h <= max; h++) {
visited = new boolean[n][n];
count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i < 0 || j < 0 || i >= n || j >= n)
continue;
if (area[i][j] <= h || visited[i][j] == true)
continue;
solve(i,j,h);
}
}
maxArea = Math.max(maxArea,count);
}
System.out.println(maxArea);
bw.flush();
bw.close();
}
public static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
area = new int[n][n];
for (int i = 0; i < n; i++) {
String temp[] = br.readLine().split(" ");
for (int j = 0; j < n; j++) {
int height = Integer.parseInt(temp[j]);
area[i][j] = height;
max = Math.max(max,height);
}
}
}
public static void solve(int a, int b, int h) {
Queue<int[]> queue = new LinkedList();
queue.offer(new int[]{a, b});
visited[a][b] = true;
while (!queue.isEmpty()) {
int coordinate[] = queue.poll();
for (int i = 0; i < 4; i++) {
int x = coordinate[0] + moveX[i];
int y = coordinate[1] + moveY[i];
if (x < 0 || y < 0 || x >= n || y >= n)
continue;
if (area[x][y] <= h || visited[x][y] == true)
continue;
queue.offer(new int[]{x, y});
visited[x][y] = true;
}
}
count++;
}
}