Seren dev's blog
article thumbnail

https://www.acmicpc.net/problem/15683

 

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감

www.acmicpc.net

1. 풀이

완전탐색으로 CCTV의 방향이 될 수 있는 모든 경우의 수를 구하여 그 중 사각지대가 최소인 경우의 크기를 구하였다.

 

완전탐색(재귀)로 모든 경우의 수를 구하므로 다음 변수들을 전역변수로 선언하였다.

- 사무실 크기 n, m

- 사무질 정보를 저장하는 rooms[n][m]을 생성

- 사각지대의 최소 크기를 저장하는 minUnwatchRoomCnt를 64로 초기화

- CCTV의 번호와 위치를 저장하기 위해 자료구조 CCTV를 생성하고, ArrayList<CCTV> cctvs를 생성

<java />
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를 출력한다.

<java />
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이면 바로 리턴한다.

<java />
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으로 바꿔버릴 수 있기 때문이다.

<java />
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으로 원상복구한다.

<java />
// 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; } } } }

 

2. 코드

<java />
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; } } } } }

 

3. 다른 풀이

재귀함수 호출 후 배열을 다시 원상복구하는 로직이 아닌, 배열을 깊은 복사하여 인자로 전달하는 방법

https://koguri.tistory.com/39

cctv 방향의 순열을 정한 다음, 한꺼번에 감시 영역을 변경하는 방법

https://minhamina.tistory.com/134

 

 

728x90
profile

Seren dev's blog

@Seren dev

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!