오늘의 키워드
•
BFS
•
구현
문제 파악 및 풀이
처음 문제를 보자마자 BFS로 풀어야겠다고 생각했다.
처음에는 입력받는 N을 빗물의 높이라고 생각했는데, 문제를 자세히 읽어보니 N은 이차원 배열의 크기만 의미하며, 빗물의 높이는 직접 고려하여 반복문으로 처리해야 했다.
•
높이 값을 줄여가면서 BFS 탐색을 수행하여 가장 많은 안전 영역을 찾는 문제였다.
•
지역의 최대 높이 값을 구한 후, 빗물의 높이를 지역 최대 높이부터 0까지 그래프 탐색 진행.
풀이 코드
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
class Main {
public static final int MAX_N = 100;
public static int n;
// 지역의 최대 높이
public static int maxHeight = Integer.MIN_VALUE;
public static int ans = Integer.MIN_VALUE;
public static int[][] matrix = new int[MAX_N][MAX_N];
public static boolean[][] isChecked;
public static Deque<int[]> stack = new ArrayDeque<>();
public static int[][] delta = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static void main(String[] args) {
// 초기값 입력.
init();
while (--maxHeight >= 0) {
isChecked = new boolean[n][n];
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 물에 잠겼거나 이미 확인했으면 패스.
if (isChecked[i][j] || matrix[i][j] <= maxHeight) continue;
bfs(i, j, maxHeight);
cnt++;
}
}
ans = Math.max(ans, cnt);
}
System.out.println(ans);
}
public static void init() {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = sc.nextInt();
maxHeight = Math.max(maxHeight, matrix[i][j]);
}
}
}
public static void bfs(int x, int y, int rain) {
stack.addLast(new int[]{x, y});
isChecked[x][y] = true;
while (!stack.isEmpty()) {
int[] poll = stack.poll();
x = poll[0];
y = poll[1];
for (int i = 0; i < 4; i++) {
int nx = x + delta[i][0];
int ny = y + delta[i][1];
if (canGo(nx, ny) && matrix[nx][ny] > rain && !isChecked[nx][ny]) {
isChecked[nx][ny] = true;
stack.addLast(new int[]{nx, ny});
}
}
}
}
public static boolean canGo(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n;
}
}
Java
복사
오늘의 회고
어려웠던 점
•
처음 문제에서 제공하는 입력값 N을 빗물의 높이로 잘못 이해해서 잠깐 혼란이 있었다. 문제를 자세히 읽는 것이 중요하다는 걸 깨달았다.
개선점
•
문제를 풀기 전에 반드시 정확한 문제 조건을 꼼꼼히 확인하고 접근하자.
•
오랜만에 BFS 문제를 풀어서 즐거웠다. DFS나 BFS와 같은 탐색 문제를 꾸준히 연습해야겠다.