설명
일단 이 문제는 예제와 결과를 보고 왜 이렇게 되는 것인지 이해조차 못했다. 한참 고민하다 해설을 보고 이해했다.
일단 다음 문장을 급하게 읽다보니, 물에 잠기지 않은 영역을 한 칸이라고 생각했다.
물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다.
예를들어 높이가 4이하인 경우 안전한 영역의 개수는 다음과 같이 5개가 되기 때문이다.
문제를 이해하니 풀이는 탐색을 사용하면 된다.
- 일단 높이는 1이상 100이하의 정수이니 1부터 100까지 높이를 수정하면서 해당 높이일 때 안전 영역을 구한다. 가장 많은 안전 영역의 개수가 답이 된다.
- 안전 영역은 주어진 높이 이상이고, 아직 방문하지 않은 지점의 동서남북을 확인하여 방문 여부를 확인한다. 해당 지점에서 더이상 방문할 수 없다면 count를 더한다.
이 문제를 풀면서 크게 두가지 고민을 했다.
첫번째 고민
그럼 BFS와 DFS 중 무엇이 적절할까?
이 문제는 한 노드에서 그 점이 방문할 수 있는 점이 더이상 없을 때까지 확인한다. 따라서 노드에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 DFS가 더 적절하다고 생각한다. 한번 두 경우를 다 작성하고, 확인해보겠다.
두번째 고민
이 문제에서 높이 범위는 1이상 100이하이다. 우리는 높이에 따라 안전 영역의 개수를 구하고, 영역의 개수가 최대일 때를 찾아야 한다. 만약 높이가 각 영역의 높이가 1부터 10사이라면, 11부터 99는 볼필요가 없다. 이러한 이유로 각 영역의 높이 중 가장 최댓값을 찾고 1부터 최댓값까지 반복하는 방식으로 작성해보았다. 물론 영역의 높이가 90부터 99에 있다면 최악이긴 하다.
확인해보니 1) 1이상 100이하 반복한 결과 메모리는 55060KB, 시간은 308ms 소모되었고, 2) 높이의 최댓값을 구해 계산했을 때는 메모리는 55104KB, 시간은 312ms 소모되었다. 이 문제에서는 반복횟수가 큰 영향을 주지 않았다.
만약 높이 범위가 1부터 10000이면 어떻게 될까? 10000-1번(높이가 10000이면 안전 영역은 없다.) 반복한 결과 메모리는 메모리는 175068KB, 시간은 700ms 소모되었다. 자릿수를 늘리면 메모리 초과가 발생했다. 확실히 범위가 충분히 커져, 반복 횟수가 늘어나니 성능에 영향을 준다는 것을 확인할 수 있었다.
코드
BFS
import java.awt.*;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N;
static int map[][];
static boolean visited[][];
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, 1, 0, -1};
static int MAX = 0;
static int answer = 1;
static Queue<Point> queue;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(st.nextToken());
map = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
int height = Integer.parseInt(st.nextToken());
MAX = Math.max(height, MAX);
map[i][j] = height;
}
}
for (int h = 1; h <= MAX; h++) {
answer = Math.max(answer, solve(h));
}
sb.append(answer);
System.out.println(sb);
}
private static int solve(int h) {
int count = 0;
visited = new boolean[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visited[i][j] && map[i][j] > h) {
count++;
BFS(i, j, h);
}
}
}
return count;
}
private static void BFS(int y, int x, int h) {
queue = new LinkedList<>();
queue.add(new Point(x, y));
visited[y][x] = true;
while (!queue.isEmpty()) {
Point now_point = queue.poll();
for (int i = 0; i < 4; i++) {
int now_y = now_point.y + dy[i];
int now_x = now_point.x + dx[i];
if (now_x < 0 || now_x > N - 1 || now_y < 0 || now_y > N - 1) {
continue;
}
if (visited[now_y][now_x]) {
continue;
}
if (map[now_y][now_x] > h) {
queue.add(new Point(now_x, now_y));
visited[now_y][now_x] = true;
}
}
}
}
}DFS
package Algorithm.P2468;
import java.awt.*;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class P2468 {
static int N;
static int map[][];
static boolean visited[][];
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, 1, 0, -1};
static int MAX = 0;
static int answer = 1;
static int count;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/Algorithm/P2468/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(st.nextToken());
map = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
int height = Integer.parseInt(st.nextToken());
MAX = Math.max(height, MAX);
map[i][j] = height;
}
}
for (int h = 1; h < MAX; h++) {
answer = Math.max(answer, solve(h));
}
sb.append(answer);
System.out.println(sb);
}
private static int solve(int h) {
count = 0;
visited = new boolean[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visited[i][j] && map[i][j] > h) {
count++;
DFS(i, j, h);
}
}
}
return count;
}
private static void DFS(int y, int x, int h) {
visited[y][x] = true;
for (int i = 0; i < 4; i++) {
int now_y = y + dy[i];
int now_x = x + dx[i];
if (now_x < 0 || now_x > N - 1 || now_y < 0 || now_y > N - 1) {
continue;
}
if (visited[now_y][now_x]) {
continue;
}
if (map[now_y][now_x] > h) {
DFS(now_y, now_x, h);
}
}
}
}느낀 점
아이디어를 떠올리는데 걸리는 시간보다 반례를 찾고 실수한 부분을 찾는데 어려웠다.
import java.awt.Point는 파라미터 순서가 x,y이다. 바꿔서 입력해서 틀렸다.
또한 Point 객체를 사용하지 않고 아래처럼 사용해도 될 것 같다.
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{x,y});- 비가 내리지 않는 경우도 있다. 이때는 높이가 0이므로 안전 영역이 하나 생긴다. 따라서 result 변수를 1로 설정해야 한다.
