https://www.acmicpc.net/problem/15683
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
풀이
완전탐색으로 CCTV의 방향이 될 수 있는 모든 경우의 수를 구하여 그 중 사각지대가 최소인 경우의 크기를 구하였다.
완전탐색(재귀)로 모든 경우의 수를 구하므로 다음 변수들을 전역변수로 선언하였다.
- 사무실 크기 n, m
- 사무질 정보를 저장하는 rooms[n][m]을 생성
- 사각지대의 최소 크기를 저장하는 minUnwatchRoomCnt를 64로 초기화
- CCTV의 번호와 위치를 저장하기 위해 자료구조 CCTV를 생성하고, ArrayList<CCTV> cctvs를 생성
static class CCTV {
int num;
int r;
int c;
public CCTV(int num, int r, int c) {
this.num = num;
this.r = r;
this.c = c;
}
}
static int n, m;
static int[][] rooms;
static ArrayList<CCTV> cctvs = new ArrayList<>();
static int minUnwatchRoomCnt = 64;
main()
- 사무실 정보를 입력받고, cctv가 있는 곳은 cctvs에 추가한다.
- install(0)을 호출한다. (0번째 cctv부터 설치)
- minUnwatchRoomCnt를 출력한다.
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
rooms = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
rooms[i][j] = Integer.parseInt(st.nextToken());
if (rooms[i][j] >= 1 && rooms[i][j] <= 5) {
cctvs.add(new CCTV(rooms[i][j], i, j));
}
}
}
install(0);
bw.write(minUnwatchRoomCnt+"");
bw.flush();
br.close();
bw.close();
}
void install(int index): index번째인 cctv의 방향을 정하여 감시 영역을 업데이트하고, 재귀적으로 함수를 호출한다.
- cctv 번호에 따라 가능한 모든 방향에 대해, install() 함수를 재귀적으로 호출한 후 recover() 함수를 호출하여 rooms 배열을 원상복구한다.
- 모든 cctv에 방향을 정하여 설치했다면, rooms[][]가 0인 칸 수를 세어 minUnwatchRoomCnt 값을 업데이트한다.
- minUnwatchRoomCnt가 0이면 바로 리턴한다.
static void install(int index) {
if (minUnwatchRoomCnt == 0) return;
if (index >= cctvs.size()) {
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
//System.out.print(rooms[i][j] + " ");
if (rooms[i][j] == 0) {
cnt++;
}
}
//System.out.println();
}
//System.out.println(cnt);
minUnwatchRoomCnt = Math.min(minUnwatchRoomCnt, cnt);
return;
}
CCTV cctv = cctvs.get(index);
int r = cctv.r;
int c = cctv.c;
// cctv 번호에 따라 가능한 모든 방향에 대해, install() 함수를 재귀적으로 호출한 후
// recover() 함수를 호출하여 원상복구
if (cctv.num == 1) {
right(r, c, index);
install(index+1);
recover(index);
down(r, c, index);
install(index+1);
recover(index);
left(r, c, index);
install(index+1);
recover(index);
up(r, c, index);
install(index+1);
recover(index);
}
else if (cctv.num == 2) {
...
}
else if (cctv.num == 3) {
...
}
else if (cctv.num == 4) {
...
}
else {
up(r, c, index);
right(r, c, index);
down(r, c, index);
left(r, c, index);
install(index+1);
recover(index);
}
}
void up(int r, int c, int index)
- rooms[r][c] 위치에서 위쪽 방향으로 올라가면서 벽을 만날 때까지 해당 위치의 rooms[][] 값을 (7 + index)으로 변경한다. (7 + index)로 업데이트하는 이유는 원래 배열에서 0~6까지의 값만 사용하기 때문이다.
주의할 점
이 때 원래 값이 0인 부분만 (7 + index)으로 변경시켜야 한다. cctv의 감시 영역이 중복될 수 있기 때문에, 이전 cctv의 감시 영역까지 0으로 바꿔버릴 수 있기 때문이다.
static void up(int r, int c, int index) {
int idx = -1;
while (r + idx >= 0 && rooms[r+idx][c] != 6) {
if (rooms[r+idx][c] == 0)
rooms[r+idx][c] = 7 + index;
idx--;
}
}
void recover(int index): rooms[][]에서 값이 (index + 7)인 부분만 0으로 원상복구한다.
// index+7인 부분만 0으로 원상복구
static void recover(int index) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (rooms[i][j] == index+7) {
rooms[i][j] = 0;
}
}
}
}
코드
import java.util.*;
import java.io.*;
public class Main {
static class CCTV {
int num;
int r;
int c;
public CCTV(int num, int r, int c) {
this.num = num;
this.r = r;
this.c = c;
}
}
static int n, m;
static int[][] rooms;
static ArrayList<CCTV> cctvs = new ArrayList<>();
static int minUnwatchRoomCnt = 64;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
rooms = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
rooms[i][j] = Integer.parseInt(st.nextToken());
if (rooms[i][j] >= 1 && rooms[i][j] <= 5) {
cctvs.add(new CCTV(rooms[i][j], i, j));
}
}
}
install(0);
bw.write(minUnwatchRoomCnt+"");
bw.flush();
br.close();
bw.close();
}
static void install(int index) {
if (minUnwatchRoomCnt == 0) return;
if (index >= cctvs.size()) {
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
//System.out.print(rooms[i][j] + " ");
if (rooms[i][j] == 0) {
cnt++;
}
}
//System.out.println();
}
//System.out.println(cnt);
minUnwatchRoomCnt = Math.min(minUnwatchRoomCnt, cnt);
return;
}
CCTV cctv = cctvs.get(index);
int r = cctv.r;
int c = cctv.c;
// cctv 번호에 따라 가능한 모든 방향에 대해, install() 함수를 재귀적으로 호출한 후
// recover() 함수를 호출하여 원상복구
if (cctv.num == 1) {
right(r, c, index);
install(index+1);
recover(index);
down(r, c, index);
install(index+1);
recover(index);
left(r, c, index);
install(index+1);
recover(index);
up(r, c, index);
install(index+1);
recover(index);
}
else if (cctv.num == 2) {
left(r, c, index);
right(r, c, index);
install(index+1);
recover(index);
up(r, c, index);
down(r, c, index);
install(index+1);
recover(index);
}
else if (cctv.num == 3) {
up(r, c, index);
right(r, c, index);
install(index+1);
recover(index);
right(r, c, index);
down(r, c, index);
install(index+1);
recover(index);
down(r, c, index);
left(r, c, index);
install(index+1);
recover(index);
left(r, c, index);
up(r, c, index);
install(index+1);
recover(index);
}
else if (cctv.num == 4) {
up(r, c, index);
left(r, c, index);
right(r, c, index);
install(index+1);
recover(index);
up(r, c, index);
right(r, c, index);
down(r, c, index);
install(index+1);
recover(index);
right(r, c, index);
down(r, c, index);
left(r, c, index);
install(index+1);
recover(index);
down(r, c, index);
left(r, c, index);
up(r, c, index);
install(index+1);
recover(index);
}
else {
up(r, c, index);
right(r, c, index);
down(r, c, index);
left(r, c, index);
install(index+1);
recover(index);
}
}
static void up(int r, int c, int index) {
int idx = -1;
while (r + idx >= 0 && rooms[r+idx][c] != 6) {
if (rooms[r+idx][c] == 0)
rooms[r+idx][c] = 7 + index;
idx--;
}
}
static void down(int r, int c, int index) {
int idx = 1;
while (r + idx < n && rooms[r + idx][c] != 6) {
if (rooms[r+idx][c] == 0)
rooms[r+idx][c] = 7 + index;
idx++;
}
}
static void left(int r, int c, int index) {
int idx = -1;
while (c + idx >= 0 && rooms[r][c+idx] != 6) {
if (rooms[r][c+idx] == 0)
rooms[r][c+idx] = 7 + index;
idx--;
}
}
static void right(int r, int c, int index) {
int idx = 1;
while (c + idx < m && rooms[r][c+idx] != 6) {
if (rooms[r][c+idx] == 0)
rooms[r][c+idx] = 7 + index;
idx++;
}
}
// index+7인 부분만 0으로 원상복구
static void recover(int index) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (rooms[i][j] == index+7) {
rooms[i][j] = 0;
}
}
}
}
}
다른 풀이
재귀함수 호출 후 배열을 다시 원상복구하는 로직이 아닌, 배열을 깊은 복사하여 인자로 전달하는 방법
cctv 방향의 순열을 정한 다음, 한꺼번에 감시 영역을 변경하는 방법
https://minhamina.tistory.com/134
728x90
'Algorithm 문제 풀이 > 백준' 카테고리의 다른 글
| [백준] 21610번 : 마법사 상어와 비바라기 - 자바[Java] (0) | 2023.10.09 |
|---|---|
| [백준] 1916번 : 최소비용 구하기(다익스트라) - 자바[Java] (0) | 2023.10.04 |
| [백준] 17140번 : 이차원 배열과 연산 - 자바[Java] (0) | 2023.10.04 |
| [백준] 17276번 : 배열 돌리기 - 자바[Java] (0) | 2023.10.01 |
| [백준] 14891번 : 톱니바퀴 - 자바[Java] (0) | 2023.09.25 |
