자바칩
[백준 / Java] 15683: 감시 (백트래킹, 구현) 본문
728x90
난이도: Gold 3
문제: https://www.acmicpc.net/problem/15683
문제
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.
 |
 |
 |
 |
 |
| 1번 | 2번 | 3번 | 4번 | 5번 |
1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.
CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.
CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.
| → | ← | ↑ | ↓ |
CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 칸을 감시할 수 없다.
0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 5위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.
| 왼쪽 상단 2: ↔, 오른쪽 하단 2: ↔ | 왼쪽 상단 2: ↔, 오른쪽 하단 2: ↕ | 왼쪽 상단 2: ↕, 오른쪽 하단 2: ↔ | 왼쪽 상단 2: ↕, 오른쪽 하단 2: ↕ |
CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.
0 0 2 0 3
0 6 0 0 0
0 0 6 6 0
0 0 0 0 0
위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.
# # 2 # 3
0 6 # 0 #
0 0 6 6 #
0 0 0 0 #
사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.
CCTV의 최대 개수는 8개를 넘지 않는다.
출력
첫째 줄에 사각 지대의 최소 크기를 출력한다.
골드3에 백트래킹이라 그런지 푸는데 어려워서 모두 나의 힘으로 풀지는 못했다.
재귀는 머리로 쉽게 그려지지가 않아서 그런지 스택오버플로우와 무한 반복을 너무 많이 마주치게 되었다.
백트래킹 문제를 더 많이 풀어봐야겠다.
나는 이 문제를 구현과 백트래킹으로 풀었다.
N, M의 데이터 수가 크지 않으면 밑으로 계속 파고들어서 여러번 2중 for문을 돌릴 수 있는 백트래킹일 가능성이 크다.
먼저 맨 아래 CCTV부터 방향을 돌리고 그 위의 CCTV 방향을 돌리고 ... 가장 마지막으로 맨 위 CCTV의 방향을 돌려야 한다.
상하좌우로 방향을 돌리는 것은 단순히 for문으로 구현을 했다.
일단 CCTV의 각 좌표와 번호를 저장할 클래스를 아래와 같이 만든다.
static class CCTV {
int x, y, n; // CCTV의 x좌표, y좌표, 번호
CCTV(int x, int y, int n) {
this.x = x;
this.y = y;
this.n = n;
}
}
이 클래스는 입력받은 번호가 CCTV에 해당할 때 ArrayList<CCTV> cctvs 에 다음과 같이 넣기 위함이다.
// 2차원 사무실 배열 초기화
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
// 0: 빈 칸
// 6: 벽
// 1 ~ 5: CCTV
office[i][j] = Integer.parseInt(st.nextToken());
// 입력받은 번호가 CCTV라면
if (office[i][j] >= 1 && office[i][j] <= 5) {
// CCTV 리스트에 x좌표, y좌표, 입력받은 번호 추가
cctvs.add(new CCTV(i, j, office[i][j]));
}
}
}
그리고 CCTV의 방향을 상하좌우로 돌리기 위한 메서드를 각각 구현한다.
해당 칸이 벽(6)이면 더이상 감시를 하지 않고 탈출을 하고, 해당 칸이 빈 칸(0)이면 해당 칸을 감시했다는 표시(-1)를 한다.
// 오른쪽 감시
public static void right(int x, int y, int[][] tempOffice) {
// y좌표 + 1부터 M까지 인덱스를 늘리면서 탐색
for (int i = y + 1; i < M; i++) {
if (tempOffice[x][i] == 6) { // 해당 칸이 벽이라면
break; // 감시 종료
} else if (tempOffice[x][i] == 0) { // 해당 칸이 빈 칸이라면
tempOffice[x][i] = -1; // 해당 칸 감시 완료
}
}
}
// 왼쪽 감시
public static void left(int x, int y, int[][] tempOffice) {
// y좌표 - 1부터 0까지 인덱스를 줄이면서 탐색
for (int i = y - 1; i >= 0; i--) {
if (tempOffice[x][i] == 6) { // 해당 칸이 벽이라면
break; // 감시 종료
} else if (tempOffice[x][i] == 0) { // 해당 칸이 빈 칸이라면
tempOffice[x][i] = -1; // 해당 칸 감시 완료
}
}
}
// 위 감시
public static void up(int x, int y, int[][] tempOffice) {
// x좌표 - 1부터 0까지 인덱스를 줄이면서 탐색
for (int i = x - 1; i >= 0; i--) {
if (tempOffice[i][y] == 6) { // 해당 칸이 벽이라면
break; // 감시 종료
} else if (tempOffice[i][y] == 0) { // 해당 칸이 빈 칸이라면
tempOffice[i][y] = -1; // 해당 칸 감시 완료
}
}
}
// 아래 감시
public static void down(int x, int y, int[][] tempOffice) {
// x좌표 + 1부터 N까지 인덱스를 늘리면서 탐색
for (int i = x + 1; i < N; i++) {
if (tempOffice[i][y] == 6) { // 해당 칸이 벽이라면
break; // 감시 종료
} else if (tempOffice[i][y] == 0) { // 해당 칸이 빈 칸이라면
tempOffice[i][y] = -1; // 해당 칸 감시 완료
}
}
}
그리고 맨 처음에는 깊이가 0이고, 입력받은 사무실이 담긴 인수를 dfs 메서드에 넘긴다.
// 첫번째 깊이(0)와 초기 사무실 배열을 인수로 넘겨서 dfs 수행
// => 첫번째 CCTV를 찾아서 방향 돌리기
dfs(0, office);
System.out.println(minSize); // 사각 지대의 최소 크기 출력
dfs 메서드는 다음과 같다.
우선 CCTV의 번호가 1일 경우만 보자.
전체 코드는 좀 나중에 보여줄 것이다.
public static void dfs(int depth, int[][] office) {
// depth가 CCTV 리스트의 크기와 같다면 모든 CCTV를 탐색한 것
if (depth == cctvs.size()) {
// 현재 사각 지대의 최소 크기(minSize)와
// 모든 CCTV를 탐색한 후 사무실 배열에 남아있는 사각지대(0)의 개수를 비교하여
// 더 작은 값을 사각 지대의 최소 크기(minSize)에 갱신
minSize = Math.min(minSize, getSize(office));
return; // 모든 CCTV를 탐색했으므로 dfs 종료
}
CCTV cctv = cctvs.get(depth); // 현재 depth에 해당하는 CCTV 가져오기
int x = cctv.x; // CCTV의 x좌표
int y = cctv.y; // CCTV의 y좌표
int n = cctv.n; // CCTV의 번호
if (n == 1) { // CCTV가 1번일 때
// 방향을 90도씩 4번 돌리기
// →, ↓, ←, ↑
for (int d = 0; d < 4; d++) {
// 매개변수로 받은 배열을 깊은 복사한 임시 사무실 배열 얻어내기
int[][] tempOffice = deepCopy(office);
if (d == 0) { // 현재 방향이 0일 때: →
right(x, y, tempOffice); // 오른쪽 감시
} else if (d == 1) { // 현재 방향이 1일 때: ↓
down(x, y, tempOffice); // 아래 감시
} else if (d == 2) { // 현재 방향이 2일 때: ←
left(x, y, tempOffice); // 왼쪽 감시
} else { // 현재 방향이 3일 때: ↑
up(x, y, tempOffice); // 위 감시
}
// 현재 깊이에서 1 더한 값과 임시 사무실 배열을 인수로 넘겨서 dfs 수행
// => 다음 CCTV를 찾아서 방향 돌리기
dfs(depth + 1, tempOffice);
}
}
... (생략)
깊이가 cctv 리스트 사이즈와 똑같으면 최소 크기를 갱신하여 dfs 메서드를 종료한다.
이것까지는 기본 백트래킹이다.
문제는 cctv의 방향을 돌리는 것이다.
1번 cctv일 경우는 오른쪽, 아래, 왼쪽, 위를 돌려야 한다.
방향을 4번 돌려야 하므로 for문으로 4번 돌리고
방향이 0일 때는 오른쪽, 1일 때는 아래, 2일 때는 왼쪽, 3일 때는 위쪽을 감시하도록 만든다.
right, down, left, up 메서드는 위에 보여줬다.
그렇다면 deepCopy메서드는 무엇일까? 깊은 복사한 배열을 받는 메서드이다.
원본 배열을 그대로 작업하게 되면 절대 안된다.
백트래킹의 특징은 작업한 이후에는 다시 작업하기 전인 원래의 값으로 되돌려줘야 한다.
이 깊은 복사 배열을 받는 것이 바로 그 역할을 한다.
이렇게 함으로써 원래 배열에는 영향을 받지 않게 한다.
방향을 돌리고 dfs로 다음 CCTV를 찾아서 방향을 돌리면 된다.
이때 깊이는 현재 깊이에서 1을 더한 값과, 깊은 복사를 받은 배열을 dfs 메서드의 인수로 넘긴다.
깊은 복사한 배열을 리턴하는 deepCopy메서드는 다음과 같다.
// 매개변수로 받은 배열을 깊은 복사하여 리턴
public static int[][] deepCopy(int[][] original) {
int[][] copy = new int[N][M];
// 2차원 배열 깊은 복사
for (int i = 0; i < N; i++) {
System.arraycopy(original[i], 0, copy[i], 0, M);
}
return copy;
}
그리고 사각지대(0)의 개수를 반환하는 메서드는 다음과 같다.
// 모든 CCTV를 탐색한 후 사무실 배열에 남아있는 사각지대(0)의 개수 리턴
public static int getSize(int[][] tempOffice) {
int size = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (tempOffice[i][j] == 0) {
size++;
}
}
}
return size;
}
이제 나머지 2~5번 CCTV일 경우도 보자.
} else if (n == 2) { // CCTV가 2번일 때
// 방향을 90도씩 2번 돌리기
// ↔, ↕
for (int d = 0; d < 2; d++) {
// 매개변수로 받은 배열을 깊은 복사한 임시 사무실 배열 얻어내기
int[][] tempOffice = deepCopy(office);
if (d == 0) { // 현재 방향이 0일 때: ↔
left(x, y, tempOffice); // 왼쪽 감시
right(x, y, tempOffice); // 오른쪽 감시
} else { // 현재 방향이 1일 때: ↕
up(x, y, tempOffice); // 위 감시
down(x, y, tempOffice); // 아래 감시
}
// 현재 깊이에서 1 더한 값과 임시 사무실 배열을 인수로 넘겨서 dfs 수행
// => 다음 CCTV를 찾아서 방향 돌리기
dfs(depth + 1, tempOffice);
}
} else if (n == 3) { // CCTV가 3번일 때
// 방향을 90도씩 4번 돌리기
// ↑→, ↓→, ←↓, ←↑
for (int d = 0; d < 4; d++) {
// 매개변수로 받은 배열을 깊은 복사한 임시 사무실 배열 얻어내기
int[][] tempOffice = deepCopy(office);
if (d == 0) { // 현재 방향이 0일 때: ↑→
up(x, y, tempOffice); // 위 감시
right(x, y, tempOffice); // 오른쪽 감시
} else if (d == 1) { // 현재 방향이 1일 때: ↓→
down(x, y, tempOffice); // 아래 감시
right(x, y, tempOffice); // 오른쪽 감시
} else if (d == 2) { // 현재 방향이 2일 때: ←↓
left(x, y, tempOffice); // 왼쪽 감시
down(x, y, tempOffice); // 아래 감시
} else { // 현재 방향이 3일 때: ←↑
left(x, y, tempOffice); // 왼쪽 감시
up(x, y, tempOffice); // 위 감시
}
// 현재 깊이에서 1 더한 값과 임시 사무실 배열을 인수로 넘겨서 dfs 수행
// => 다음 CCTV를 찾아서 방향 돌리기
dfs(depth + 1, tempOffice);
}
} else if (n == 4) { // CCTV가 4번일 때
// 방향을 90도씩 4번 돌리기
// ←↑→, ↑↓→, ←↓→, ←↑↓
for (int d = 0; d < 4; d++) {
// 매개변수로 받은 배열을 깊은 복사한 임시 사무실 배열 얻어내기
int[][] tempOffice = deepCopy(office);
if (d == 0) { // 현재 방향이 0일 때: ←↑→
left(x, y, tempOffice); // 왼쪽 감시
up(x, y, tempOffice); // 위 감시
right(x, y, tempOffice); // 오른쪽 감시
} else if (d == 1) { // 현재 방향이 1일 때: ↑↓→
up(x, y, tempOffice); // 위 감시
right(x, y, tempOffice); // 오른쪽 감시
down(x, y, tempOffice); // 아래 감시
} else if (d == 2) { // 현재 방향이 2일 때: ←↓→
right(x, y, tempOffice); // 오른쪽 감시
down(x, y, tempOffice); // 아래 감시
left(x, y, tempOffice); // 왼쪽 감시
} else { // 현재 방향이 3일 때: ←↑↓
down(x, y, tempOffice); // 아래 감시
left(x, y, tempOffice); // 왼쪽 감시
up(x, y, tempOffice); // 위 감시
}
// 현재 깊이에서 1 더한 값과 임시 사무실 배열을 인수로 넘겨서 dfs 수행
// => 다음 CCTV를 찾아서 방향 돌리기
dfs(depth + 1, tempOffice);
}
} else { // CCTV가 5번일 때
// ←↑↓→ 한 방향밖에 없으므로 for문 돌리지 않아도 됨
// 매개변수로 받은 배열을 깊은 복사한 임시 사무실 배열 얻어내기
int[][] tempOffice = deepCopy(office);
right(x, y, tempOffice); // 오른쪽 감시
down(x, y, tempOffice); // 아래 감시
left(x, y, tempOffice); // 왼쪽 감시
up(x, y, tempOffice); // 위 감시
// 현재 깊이에서 1 더한 값과 임시 사무실 배열을 인수로 넘겨서 dfs 수행
// => 다음 CCTV를 찾아서 방향 돌리기
dfs(depth + 1, tempOffice);
}
1번을 이해했으면 2~5번은 그렇게 어렵지 않을 것이다.
내가 작성한 전체 코드는 남들보다 좀 길다.
문제를 풀면서 200줄이 넘은 적은 처음이다.
전체 코드
|
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class P15683_감시 {
static int N, M; // 사무실의 세로, 가로 크기
static ArrayList<CCTV> cctvs = new ArrayList<>(); // CCTV(x좌표, y좌표, 번호) 리스트
static int minSize = Integer.MAX_VALUE; // 사각 지대의 최소 크기
static class CCTV {
int x, y, n; // CCTV의 x좌표, y좌표, 번호
CCTV(int x, int y, int n) {
this.x = x;
this.y = y;
this.n = n;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int[][] office = new int[N][M]; // 2차원 사무실 배열
// 2차원 사무실 배열 초기화
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
// 0: 빈 칸
// 6: 벽
// 1 ~ 5: CCTV
office[i][j] = Integer.parseInt(st.nextToken());
// 입력받은 번호가 CCTV라면
if (office[i][j] >= 1 && office[i][j] <= 5) {
// CCTV 리스트에 x좌표, y좌표, 입력받은 번호 추가
cctvs.add(new CCTV(i, j, office[i][j]));
}
}
}
// 첫번째 깊이(0)와 초기 사무실 배열을 인수로 넘겨서 dfs 수행
// => 첫번째 CCTV를 찾아서 방향 돌리기
dfs(0, office);
System.out.println(minSize); // 사각 지대의 최소 크기 출력
}
public static void dfs(int depth, int[][] office) {
// depth가 CCTV 리스트의 크기와 같다면 모든 CCTV를 탐색한 것
if (depth == cctvs.size()) {
// 현재 사각 지대의 최소 크기(minSize)와
// 모든 CCTV를 탐색한 후 사무실 배열에 남아있는 사각지대(0)의 개수를 비교하여
// 더 작은 값을 사각 지대의 최소 크기(minSize)에 갱신
minSize = Math.min(minSize, getSize(office));
return; // 모든 CCTV를 탐색했으므로 dfs 종료
}
CCTV cctv = cctvs.get(depth); // 현재 depth에 해당하는 CCTV 가져오기
int x = cctv.x; // CCTV의 x좌표
int y = cctv.y; // CCTV의 y좌표
int n = cctv.n; // CCTV의 번호
if (n == 1) { // CCTV가 1번일 때
// 방향을 90도씩 4번 돌리기
// →, ↓, ←, ↑
for (int d = 0; d < 4; d++) {
// 매개변수로 받은 배열을 깊은 복사한 임시 사무실 배열 얻어내기
int[][] tempOffice = deepCopy(office);
if (d == 0) { // 현재 방향이 0일 때: →
right(x, y, tempOffice); // 오른쪽 감시
} else if (d == 1) { // 현재 방향이 1일 때: ↓
down(x, y, tempOffice); // 아래 감시
} else if (d == 2) { // 현재 방향이 2일 때: ←
left(x, y, tempOffice); // 왼쪽 감시
} else { // 현재 방향이 3일 때: ↑
up(x, y, tempOffice); // 위 감시
}
// 현재 깊이에서 1 더한 값과 임시 사무실 배열을 인수로 넘겨서 dfs 수행
// => 다음 CCTV를 찾아서 방향 돌리기
dfs(depth + 1, tempOffice);
}
} else if (n == 2) { // CCTV가 1번일 때
// 방향을 90도씩 2번 돌리기
// ↔, ↕
for (int d = 0; d < 2; d++) {
// 매개변수로 받은 배열을 깊은 복사한 임시 사무실 배열 얻어내기
int[][] tempOffice = deepCopy(office);
if (d == 0) { // 현재 방향이 0일 때: ↔
left(x, y, tempOffice); // 왼쪽 감시
right(x, y, tempOffice); // 오른쪽 감시
} else { // 현재 방향이 1일 때: ↕
up(x, y, tempOffice); // 위 감시
down(x, y, tempOffice); // 아래 감시
}
// 현재 깊이에서 1 더한 값과 임시 사무실 배열을 인수로 넘겨서 dfs 수행
// => 다음 CCTV를 찾아서 방향 돌리기
dfs(depth + 1, tempOffice);
}
} else if (n == 3) { // CCTV가 3번일 때
// 방향을 90도씩 4번 돌리기
// ↑→, ↓→, ←↓, ←↑
for (int d = 0; d < 4; d++) {
// 매개변수로 받은 배열을 깊은 복사한 임시 사무실 배열 얻어내기
int[][] tempOffice = deepCopy(office);
if (d == 0) { // 현재 방향이 0일 때: ↑→
up(x, y, tempOffice); // 위 감시
right(x, y, tempOffice); // 오른쪽 감시
} else if (d == 1) { // 현재 방향이 1일 때: ↓→
down(x, y, tempOffice); // 아래 감시
right(x, y, tempOffice); // 오른쪽 감시
} else if (d == 2) { // 현재 방향이 2일 때: ←↓
left(x, y, tempOffice); // 왼쪽 감시
down(x, y, tempOffice); // 아래 감시
} else { // 현재 방향이 3일 때: ←↑
left(x, y, tempOffice); // 왼쪽 감시
up(x, y, tempOffice); // 위 감시
}
// 현재 깊이에서 1 더한 값과 임시 사무실 배열을 인수로 넘겨서 dfs 수행
// => 다음 CCTV를 찾아서 방향 돌리기
dfs(depth + 1, tempOffice);
}
} else if (n == 4) { // CCTV가 4번일 때
// 방향을 90도씩 4번 돌리기
// ←↑→, ↑↓→, ←↓→, ←↑↓
for (int d = 0; d < 4; d++) {
// 매개변수로 받은 배열을 깊은 복사한 임시 사무실 배열 얻어내기
int[][] tempOffice = deepCopy(office);
if (d == 0) { // 현재 방향이 0일 때: ←↑→
left(x, y, tempOffice); // 왼쪽 감시
up(x, y, tempOffice); // 위 감시
right(x, y, tempOffice); // 오른쪽 감시
} else if (d == 1) { // 현재 방향이 1일 때: ↑↓→
up(x, y, tempOffice); // 위 감시
right(x, y, tempOffice); // 오른쪽 감시
down(x, y, tempOffice); // 아래 감시
} else if (d == 2) { // 현재 방향이 2일 때: ←↓→
right(x, y, tempOffice); // 오른쪽 감시
down(x, y, tempOffice); // 아래 감시
left(x, y, tempOffice); // 왼쪽 감시
} else { // 현재 방향이 3일 때: ←↑↓
down(x, y, tempOffice); // 아래 감시
left(x, y, tempOffice); // 왼쪽 감시
up(x, y, tempOffice); // 위 감시
}
// 현재 깊이에서 1 더한 값과 임시 사무실 배열을 인수로 넘겨서 dfs 수행
// => 다음 CCTV를 찾아서 방향 돌리기
dfs(depth + 1, tempOffice);
}
} else { // CCTV가 5번일 때
// ←↑↓→ 한 방향밖에 없으므로 for문 돌리지 않아도 됨
// 매개변수로 받은 배열을 깊은 복사한 임시 사무실 배열 얻어내기
int[][] tempOffice = deepCopy(office);
right(x, y, tempOffice); // 오른쪽 감시
down(x, y, tempOffice); // 아래 감시
left(x, y, tempOffice); // 왼쪽 감시
up(x, y, tempOffice); // 위 감시
// 현재 깊이에서 1 더한 값과 임시 사무실 배열을 인수로 넘겨서 dfs 수행
// => 다음 CCTV를 찾아서 방향 돌리기
dfs(depth + 1, tempOffice);
}
}
// 매개변수로 받은 배열을 깊은 복사하여 리턴
public static int[][] deepCopy(int[][] original) {
int[][] copy = new int[N][M];
// 2차원 배열 깊은 복사
for (int i = 0; i < N; i++) {
System.arraycopy(original[i], 0, copy[i], 0, M);
}
return copy;
}
// 오른쪽 감시
public static void right(int x, int y, int[][] tempOffice) {
// y좌표 + 1부터 M까지 인덱스를 늘리면서 탐색
for (int i = y + 1; i < M; i++) {
if (tempOffice[x][i] == 6) { // 해당 칸이 벽이라면
break; // 감시 종료
} else if (tempOffice[x][i] == 0) { // 해당 칸이 빈 칸이라면
tempOffice[x][i] = -1; // 해당 칸 감시 완료
}
}
}
// 왼쪽 감시
public static void left(int x, int y, int[][] tempOffice) {
// y좌표 - 1부터 0까지 인덱스를 줄이면서 탐색
for (int i = y - 1; i >= 0; i--) {
if (tempOffice[x][i] == 6) { // 해당 칸이 벽이라면
break; // 감시 종료
} else if (tempOffice[x][i] == 0) { // 해당 칸이 빈 칸이라면
tempOffice[x][i] = -1; // 해당 칸 감시 완료
}
}
}
// 위 감시
public static void up(int x, int y, int[][] tempOffice) {
// x좌표 - 1부터 0까지 인덱스를 줄이면서 탐색
for (int i = x - 1; i >= 0; i--) {
if (tempOffice[i][y] == 6) { // 해당 칸이 벽이라면
break; // 감시 종료
} else if (tempOffice[i][y] == 0) { // 해당 칸이 빈 칸이라면
tempOffice[i][y] = -1; // 해당 칸 감시 완료
}
}
}
// 아래 감시
public static void down(int x, int y, int[][] tempOffice) {
// x좌표 + 1부터 N까지 인덱스를 늘리면서 탐색
for (int i = x + 1; i < N; i++) {
if (tempOffice[i][y] == 6) { // 해당 칸이 벽이라면
break; // 감시 종료
} else if (tempOffice[i][y] == 0) { // 해당 칸이 빈 칸이라면
tempOffice[i][y] = -1; // 해당 칸 감시 완료
}
}
}
// 모든 CCTV를 탐색한 후 사무실 배열에 남아있는 사각지대(0)의 개수 리턴
public static int getSize(int[][] tempOffice) {
int size = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (tempOffice[i][j] == 0) {
size++;
}
}
}
return size;
}
}
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| [백준 / Java] 1759: 섬의 개수 (BFS) (0) | 2024.07.20 |
|---|---|
| [백준 / Java] 1759: 암호 만들기 (백트래킹) (1) | 2024.07.19 |
| [백준 / Java] 3184: 양 (BFS) (0) | 2024.07.14 |
| [백준 / Java] 1303: 전쟁 - 전투 (BFS) (0) | 2024.07.14 |
| [백준 / Java] 10026: 적록색약 (BFS) (0) | 2024.07.11 |
'알고리즘/백준' Related Articles
more
