[Java] 백준(실버-1) 2468번 - 안전 영역
문제 풀이
이번 문제는 BFS를 이용한 그래프 탐색을 이용해 풀 수 있다.
아이디어 도출
BFS를 통해 탐색하면서 연결된 노드의 개수를 구하는 것과 높이별로 탐색을 구분하여 진행해야 한다는 점을 유의하면 쉽게 풀 수 있다.
- 높이정보를 입력받으며 높이별 목록을 만든다.
- 구한 높이별로 배열을 탐색하며 BFS를 호출하여 연결된 노드를 구한다.
이때, 높이별로 2차원배열을 탐색하니 시간복잡도는
O(N^3)이 된다. - BFS의 호출횟수가 해당 높이의 안전영역의 개수가 되므로 높이별로 안전영역의 개수를 센다.
- 모든 높이를 순회하며 가장 높은 안전영역의 개수를 구하면 된다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
import java.io.*;
import java.util.*;
class Main {
// 상, 하, 좌, 우로 탐색할 dx, dy 배열 선언
static int[] dx = new int[]{0, 1, 0, -1};
static int[] dy = new int[]{1, 0, -1, 0};
// 방문 여부를 기록할 배열 선언
static boolean[][] visited;
// 높이 여부를 담을 배열 선언
static int[][] arr;
// 배열 크기인 N*M의 N, M
static int N, M;
// 높이별 안전영역 갯수를 담을 변수
static int safeZoneCnt;
// 모든 높이 중 가장 많은 안전영역 개수를 담을 변수
static int maxSafeZoneCnt;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
M = N;
arr = new int[N][M];
// 모든 높이를 담을 hashSet
TreeSet<Integer> heights_set = new TreeSet<>();
/**
* 입력받는 높이 정보를 arr 배열에 삽입
* 이때, 높이정보를 hashSet에 함께 삽입
*/
for(int i=0; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
heights_set.add(arr[i][j]);
}
}
// 높이정보를 담은 hashSet을 ArrayList에 담는다.
ArrayList<Integer> heights = new ArrayList<>(heights_set);
// 모든 안전영역 개수중 가장 많은 안전영역을 구하기 위해 초기화
maxSafeZoneCnt = 0;
// 높이마다 순회
for(int i=0; i<heights.size(); i++) {
// 높이마다 방문 여부를 비교해야 하기 때문에 높이별로 방문 배열 초기화
visited = new boolean[N][M];
// 높이별 안전영역 개수를 구하기 위해 safeZoneCnt 초기화
safeZoneCnt = 0;
/**
* 높이마다 arr 배열을 순회하면서 BFS를 호출
* BFS 호출횟수가 안전영역의 개수가 된다.
* BFS 호출 이후 해당 높이만큼 잠겨야 하기에 해당 원소들을 0으로 갱신
*/
for(int x=0; x<N; x++) {
for(int y=0; y<M; y++) {
if(!visited[x][y] && arr[x][y] != 0) {
safeZoneCnt++;
BFS(x, y);
}
if(heights.get(i) == arr[x][y]) {
arr[x][y] = 0;
}
}
}
// 높이별로 구한 안전영역의 개수 중 가장 높은 값을 maxSafeZoneCnt에 저장
maxSafeZoneCnt = Math.max(maxSafeZoneCnt, safeZoneCnt);
}
bw.write(maxSafeZoneCnt+"\n");
bw.close();
br.close();
}
/**
* BFS 함수
*/
static void BFS(int x, int y) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x, y});
visited[x][y] = true;
while(!q.isEmpty()) {
int[] now = q.poll();
for(int dir=0; dir<4; dir++) {
int i = now[0] + dx[dir];
int j = now[1] + dy[dir];
if(isRange(i, j)) {
if(!visited[i][j] && arr[i][j] != 0) {
visited[i][j] = true;
q.offer(new int[]{i, j});
}
}
}
}
}
static boolean isRange(int x, int y) {
if(0<=x && 0<=y && x<N && y<M) {
return true;
}
return false;
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.