백준 2468번: 안전 영역[JAVA]
https://www.acmicpc.net/problem/2468
2468번: 안전 영역
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는
www.acmicpc.net
[정답 코드]
import java.io.*;
import java.util.*;
public class Main {
static int N,result, count, nx, ny;
static int[][] graph;
static boolean[][] visited;
static int[] dx = {0, 0, 1, -1}; // 상하좌우 4방탐색
static int[] dy = {1, -1, 0, 0};
static ArrayList<Integer> list = new ArrayList<>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
// graph 초기화
N = Integer.parseInt(st.nextToken());
graph = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; j++) {
graph[i][j] = Integer.parseInt(st.nextToken());
// 건물의 높이들이 담긴 리스트
if (!list.contains(graph[i][j])) { // 중복체크
list.add(graph[i][j]);
}
}
}
result = 1;
for (Integer height : list) { // 0부터 끝까지 탐색하는것은 비효율적이기 때문에 리스트 활용
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] && graph[i][j] >= height) {
count++;
dfs(height, i, j);
}
}
}
result = Math.max(result, count); // 새로탐색한결과 중에 더 큰값 저장
}
System.out.println(result);
}
static void dfs(int height, int x, int y) {
visited[x][y] = true;
// 4방탐색
for (int i = 0; i < 4; i++) {
nx = x + dx[i];
ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < N) { // 그래프 범위 안에 있을 경우
if (!visited[nx][ny]) { // 방문하지 않은 건물인 경우
if (graph[nx][ny] >= height) { // 그 건물이 물의 높이보다 높을 경우
dfs(height, nx, ny); // 상하좌우 인접한 건물을 찾는다
}
}
}
}
}
}
[설명]
이 문제는 완전탐색 알고리즘이다. 그중 dfs 알고리즘을 활용해 문제를 해결했다. dx/dy 기법을 활용한 4방 탐색도 활용했다. 먼저 2차원 배열을 선언해준다. 이 때 중요한점이 입력값들을 중복값을 체크하며 리스트에 담아놔야한다. 그렇지 않을 경우는 비의 양을 0부터 끝까지 중복탐색해야해서 메모리 초과가 나거나 비효율적이다.
dfs 로직은 4방탐색을 하며 그 범위가 방문하지않은 건물이며 그 건물이 물의 높이 보다 높을경우 dfs를 다시 실행한다.
그 후 결과값을 비교해 최대값을 출력한다.
'코딩테스트' 카테고리의 다른 글
| 백준 13305번: 주유소[JAVA] (2) | 2024.01.26 |
|---|---|
| 백준 9017번: 크로스 컨트리[JAVA] (1) | 2024.01.25 |
| 백준 1182번: 부분수열의 합[JAVA] (0) | 2023.11.23 |
| 백준 1759번: 암호 만들기[JAVA] (0) | 2023.11.21 |
| 백준 1699번: 제곱수의 합[JAVA] (0) | 2023.11.16 |
