백준 2468번 : 안전 영역
이번 문제와 다음 문제는 간단하게 작성할 것이다.
기본적으로 탐색 관련은 이전에도 계속 작성했기 때문에 넘어갈 것이다.
DFS와 BFS의 기본은 DFS와 BFS 문제
좌표 탐색 카운팅은 단지번호붙이기 문제
를 참조하면 된다.
이번과 다음 문제를 왜 간단하게 작성하냐면, 탐색 알고리즘은 동일하지만 이번 문제는 탐색을 여러번 반복시키는 문제이고, 다음 문제는 대각선 탐색이 포함되어 있어 각각의 케이스를 기억하기 위해서 작성하는 것이기 때문이다.
다시 말해 아주 복잡한 문제는 아니다.
이번 문제는 정사각형의 N*N 그래프가 주어지고 해당 그래프의 각 요소들은 건물의 높이를 표현한다.
이 건물들이 침수 될 경우 안전 영역이 최대 몇 구역까지 있을 수 있는지를 리턴하는 문제이다.
즉, 0부터 N까지의 경우를 시뮬레이션하고 침수되지 않은 구역이 가장 많은 경우를 리턴하면 된다.
간단하게 작성한다했으니 바로 메인 로직으로 접근할 것이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
arr = new int[n][n];
StringTokenizer st;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
max = Math.max(max, arr[i][j]);
}
}
int safeArea = 0;
for (int i = 0; i <= max; i++) {
visited = new boolean[n][n];
int count = 0;
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (arr[j][k] > i && !visited[j][k]) {
count++;
// dfs(i,j,k);
bfs(i,j,k);
}
}
}
safeArea = Math.max(safeArea, count);
}
System.out.println(safeArea);
}
로직을 처음부터 순서대로 볼 것이다.
우선 그래프를 표현한다.
1
2
3
4
5
6
7
8
StringTokenizer st;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
max = Math.max(max, arr[i][j]);
}
}
이 그래프 표현 방식은 항상 어떤 문제를 풀든 등장했지만 max의 등장 의미에 대해 궁금할 수 있다.
이 max 변수는 그래프를 표현함과 동시에 그래프 내부의 가장 높은 건물의 값을 저장하는 역할을 하는데, 이는 모든 건물이 침수될 때까지의 상황을 시뮬레이션 해야하기 때문에 필요한 값이다.
즉, 시뮬레이션 최대 횟수라고 생각하면 된다.
다음으로는 탐색을 실행시켜야 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int safeArea = 0;
for (int i = 0; i <= max; i++) {
visited = new boolean[n][n];
int count = 0;
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (arr[j][k] > i && !visited[j][k]) {
count++;
// dfs(i,j,k);
bfs(i,j,k);
}
}
}
safeArea = Math.max(safeArea, count);
}
safeArea 변수에는 문제에서 요구하는 결과를 저장할 것이다.
즉, 이 safeArea 변수에는 안전 구역의 최댓값이 저장된다.
앞서 말했듯이 반복문은 건물의 최대 높이까지 반복된다.
이 횟수 만큼 탐색 알고리즘을 활용할 것이다.
그렇기 때문에, 횟수가 반복될 때마다 visited 방문 여부 배열을 초기화해야하고, count 역시 구역의 개수를 세는 것이기 때문에 각 시뮬레이션이 시작될 때마다 초기화 해주어야 한다.
탐색이 시작되는 조건은 현재 i의 값 보다 큰 요소는 물에 잠기지 않는 것이므로 i보다 클때, 그리고 방문하지 않았을 때 탐색이 시작된다.
마찬가지로 탐색이 시작되는 것은 해당 구역이 안전 구역이라는 것이기 때문에 count의 개수를 올려준다.
이후 반복문이 시작되는데 매개변수에서 j와 k는 좌표를 의미하고 i는 다음 탐색 기준을 잡아주기 위해 같이 삽입되었다.
DFS / BFS 로직은 언제나와 같다.
다만 다음 위치를 잡는 조건이 그때그때 바뀌기 때문에 i를 활용하는 것이 다르다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static void dfs(int i, int x, int y) {
visited[x][y] = true;
for (int l = 0; l < 4; l++) {
int nx = x + dx[l];
int ny = y + dy[l];
if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
if (arr[nx][ny] > i && !visited[nx][ny]) {
dfs(i, nx, ny);
}
}
}
}
public static void bfs(int i, int x, int y) {
visited[x][y] = true;
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x,y});
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int l = 0; l < 4; l++) {
int nx = cur[0] + dx[l];
int ny = cur[1] + dy[l];
if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
if (arr[nx][ny] > i && !visited[nx][ny]) {
q.offer(new int[]{nx,ny});
visited[nx][ny] = true;
}
}
}
}
}
보면 배열 인덱스로 들어가는 변수가 달라 헷갈릴 순 있지만 기본적인 탐색 방법일 뿐이고 다음 탐색 위치를 분기하는 조건만 주의하면 된다.
이제 각 시뮬레이션 마다
1
safeArea = Math.max(safeArea, count);
를 사용해 safeArea에 최댓값을 비교하여 넣어준 다음, 시뮬레이션이 종료되면 safeArea를 리턴하면 된다.
전체 소스코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int[][] arr;
static boolean[][] visited;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int n, max = 0;
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
arr = new int[n][n];
StringTokenizer st;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
max = Math.max(max, arr[i][j]);
}
}
int safeArea = 0;
for (int i = 0; i <= max; i++) {
visited = new boolean[n][n];
int count = 0;
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (arr[j][k] > i && !visited[j][k]) {
count++;
// dfs(i,j,k);
bfs(i,j,k);
}
}
}
safeArea = Math.max(safeArea, count);
}
System.out.println(safeArea);
}
public static void dfs(int i, int x, int y) {
visited[x][y] = true;
for (int l = 0; l < 4; l++) {
int nx = x + dx[l];
int ny = y + dy[l];
if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
if (arr[nx][ny] > i && !visited[nx][ny]) {
dfs(i, nx, ny);
}
}
}
}
public static void bfs(int i, int x, int y) {
visited[x][y] = true;
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x,y});
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int l = 0; l < 4; l++) {
int nx = cur[0] + dx[l];
int ny = cur[1] + dy[l];
if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
if (arr[nx][ny] > i && !visited[nx][ny]) {
q.offer(new int[]{nx,ny});
visited[nx][ny] = true;
}
}
}
}
}
}
각각 위에서 아래로 DFS, BFS 결과이다.
간단하게 작성한다고 했는데 길어진 것 같다.
여튼, 만약 탐색 알고리즘을 활용하여 여러 번 시뮬레이션을 해야하는 문제가 있다면 현재 문제를 참고하면 된다.