어떻게 풀어야 할까
항상 문제는 Brute Force를 먼저 생각한다. 문제를 보자마자 어떤 알고리즘을 사용해서 어떻게 풀어야 할지 아는 것이 가능할까. 적어도 나는 안된다... 그렇기 때문에 일단 문제의 정답을 구할 수 있는 알고리즘을 구하고, 문제에서 요구하는 시간 복잡도 안에 해결하기 위해 최적화를 진행한다.
해당 문제는 물에 잠기지 않은 영역의 갯수 중 최대값을 구하는 문제이다. 물의 높이는 선형적으로 점차 증가하고, 각각의 경우의 수를 기록하여 그 중 최대값을 출력하면 된다. 물에 잠기지 않는 안전 영역은 DFS를 통해서 구할 수 있다. DFS를 통해 연결 요소를 각각의 영역에서 반복한다, 즉 안전 영역의 갯수를 물에 아직 잠기지 않고, 방문한적 없는 모든 영역에서 DFS를 통해 DFS가 실행되는 횟수가 곧 안전 영역의 수이다.
결국 DFS + Brute Force 로 해당 문제를 풀 수 있다.
시간 복잡도
해당 문제를 어떻게 풀어야 할지 알았으면 해당 알고리즘이 시간 내에 가능한지 생각해봐야 한다. 최악의 경우를 생각해보자. 최악의 경우는 가로 세로가 100 이고, 물의 높이가 1~100까지 모두 존재하는 경우일 것이다. 해당 경우의 시간 복잡도는 모든 물의 높이를 계산해야 하므로 N, 각 영역에 대해 DFS를 돌리는 횟수 (N + 1) * N / 2, DFS의 시간복잡도 O(n+e), 결국 O(N^3(n+e)) -> O(N^4) 이고 N <= 100 이므로 해당 문제는 1초안에 풀 수 있다.
문제 풀이 알고리즘
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, maxWaterDepth, maxSafeZoneCnt;
static int[][] sunkPos;
static boolean[][] visited;
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
input();
findMaxSafeZone();
output();
}
public static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
sunkPos = new int[N][N];
visited = new boolean[N][N];
maxWaterDepth = 0;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
sunkPos[i][j] = Integer.parseInt(st.nextToken());
if (maxWaterDepth < sunkPos[i][j]) {
maxWaterDepth = sunkPos[i][j];
}
}
}
}
public static void findMaxSafeZone() {
maxSafeZoneCnt = 0;
for (int waterDepth = 0; waterDepth < maxWaterDepth + 1; waterDepth++) {
visited = new boolean[N][N];
int safeZoneCnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visited[i][j] && sunkPos[i][j] > waterDepth) {
safeZoneCnt += DFS(i, j, waterDepth);
}
}
}
maxSafeZoneCnt = Math.max(maxSafeZoneCnt, safeZoneCnt);
}
}
public static int DFS(int x, int y, int waterDepth) {
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (newX >= 0 && newY >= 0 && newX < N && newY < N) {
if (!visited[newX][newY] && sunkPos[newX][newY] > waterDepth) {
DFS(newX, newY, waterDepth);
}
}
}
return 1;
}
public static void output() {
System.out.println(maxSafeZoneCnt);
}
}
문제 풀이는 위에서 설명한 DFS + Brute Force 를 그대로 구현해주면 된다. maxWaterDepth를 따로 구해준 이유는 어차피 최대 값을 넘어서는 비가 오면, 모든 영역이 잠기기 때문에 구할 필요가 없기 때문이다.
참고: 물의 높이가 최대 N인지 모르고, 테스트 케이스만 보고 1자리 수만 된다고 생각했다. 그리고 틀렸다... 항상 문제를 잘 읽어서 조건을 잘 체크하자.
'Koala - 9기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
[백준/Python3] 17626번 Four Squares (0) | 2023.01.06 |
---|---|
[백준/Python] 9207번 페그 솔리테어 (0) | 2023.01.03 |
[백준/C++] 17142번 연구소 3 (0) | 2023.01.02 |
[백준/c++]14391번 종이조각 비트마스킹 풀이 (4) | 2023.01.01 |
[백준/Python] 13459번 구슬 탈출 (0) | 2023.01.01 |