문제 설명
cctv를 적절하게 회전시켜 감시하지 못하는 구역의 개수를 최소화하는 문제
접근
처음에 브루트포스 방식 말고 무언가 규칙을 통해서 해답을 얻을 수 있지 않을까해서 이상한 노가다를 시작했다.. 결론부터 말하자면 없는 것 같다ㅠ
첫 번째 시도에서는 임의의 고정된 순서대로 cctv의 여러 회전 중 최적해를 고르고, 이에 이어서 그 해에 대한 다음 cctv의 최적해를 고르는 식으로 하였다. 그리고 당연히 이는 문제가 있었다.
아래와 같은 예시에서 정답인 8이 아닌 9가 나온다. 따라서 그 다음으로 생각했던 풀이가 cctv의 탐색 범위가 큰 것부터 최적해를 찾아가는 것.
이는 단순히 cctv 배열을 sorting하는 것으로 만들 수 있었다.
Arrays.sort(cctv, (o1, o2)->o2[2]-o1[2]); // 2번째 값은 cctv 타입번호이는 위의 예시에 대해서는 잘 동작하였지만 여전히 틀렸다는 결과를 얻었다.. 이 부분에서 30분 이상을 태워서 때문에 더 이상 다른 방법을 찾을 생각이 들지 않았다..
혹시 몰라 다른 분께 조언을 들었는데 역시 브루트포스로 하라는 말을 듣고 브루트포스로 모든 경우에 대해 cctv를 돌려보는 것으로 코드를 수정했다.
// 수정 전. 모든 cctv에 대해 모니터링 수행
private static int monitoring(int[] cctv, int[][] arr) {
if(cctv[0]==0) return 0;
int type = cctv[2];
int rotate = 0;
int max = 0;
// cctv 회전
for(int i=0; i<4; i++) {
int temp = 0;
// 현재 방향의 상하좌우 다 체크
for(int j=0; j<4; j++) {
if((CCTV[type] & 1<<(i+j)%4) == 0)
continue;
int r = cctv[0] + dr[j%4];
int c = cctv[1] + dc[j%4];
while(arr[r][c]!=6) {
if(arr[r][c]==0)
temp++;
r += dr[j%4];
c += dc[j%4];
}
}
if(max<temp) {
max = temp;
rotate = i;
}
}
// 결정한 방향에 맞게 arr 업데이트
for(int j=0; j<4; j++) {
if((CCTV[type] & 1<<(rotate+j)%4) == 0)
continue;
int r = cctv[0] + dr[j%4];
int c = cctv[1] + dc[j%4];
while(arr[r][c]!=6) {
if(arr[r][c]==0)
arr[r][c] = 7;
r += dr[j%4];
c += dc[j%4];
}
}
return max;
}// 수정 후. 재귀로 모든 케이스에 대해 구하고 최적해 반환하도록 변경
private static int monitoring(int idx, int[][] cctv, int[][] arr) {
if(cctv[idx][0]==0) return 0; // CCTV 없으면 그냥 종료
int type = cctv[idx][2]; // CCTV 종류
int max = 0; // 최대 감시구역 개수
// cctv 회전
for(int i=0; i<4; i++) {
int temp = 0; // 해당 방향에서의 탐색 시작
int[][] copy = new int[arr.length][arr[0].length];
for(int r=0; r<arr.length; r++)
System.arraycopy(arr[r], 0, copy[r], 0, arr[r].length);
// 현재 방향의 상하좌우 다 체크
for(int j=0; j<4; j++) {
if((CCTV[type] & 1<<(i+j)%4) == 0)
continue;
int r = cctv[idx][0] + dr[j%4];
int c = cctv[idx][1] + dc[j%4];
while(copy[r][c]!=6) {
if(copy[r][c]==0) {
temp++;
copy[r][c] = 7;
}
r += dr[j%4];
c += dc[j%4];
}
}
temp += monitoring(idx+1, cctv, copy);
if(max<temp) {
max = temp;
}
}
return max;
}전체 코드에 대해 주석을 통해 설명하자면 다음과 같다.
public static void main(String[] args) throws Exception {
// 입력 받는 부분
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] arr = getArr(N, M); // 가장자리 벽을 세워 맵 만듦
int[][] cctv = new int[9][3]; // CCTV 정보 저장할 배열
int space = 0; // 미감시 구역
int idx = 0; // CCTV 개수
for(int n=1; n<=N; n++) {
st = new StringTokenizer(br.readLine());
for(int m=1; m<=M; m++) {
int temp = Integer.parseInt(st.nextToken());
arr[n][m] = temp; // 일단 저장
if(temp>0 && temp<=5) // CCTV면 CCTV 배열에 저장
cctv[idx++] = new int[] {n, m, temp};
else if(temp==0) // 미감시 구역 카운트
space++;
}
}
// 연산 부분
space -= monitoring(0, cctv, arr); // 전체 CCTV 가동하여 감시구역 제외하기
System.out.println(space); // 미감시 구역 개수 출력
}public static int[] dr = {1, 0, -1, 0}; // 북서남동..인데 이는 사실 중요하지 않음!
public static int[] dc = {0, -1, 0, 1};
//CCTV별 탐색 비트마스크
public static int[] CCTV = {0b0000, 0b1000, 0b1010, 0b1001, 0b1011, 0b1111};
private static int monitoring(int idx, int[][] cctv, int[][] arr) {
if(cctv[idx][0]==0) return 0; // CCTV 없으면 그냥 종료
int type = cctv[idx][2]; // CCTV 종류
int max = 0; // 최대 감시구역 개수
// cctv 회전
for(int i=0; i<4; i++) {
// i는 해당 cctv를 90도로 몇번 돌렸는지를 의미. 4가지로 돌릴 수 있으니 4번
int temp = 0; // 해당 방향에서의 탐색 시작
// 선택한 방향에 대해 계산하고 재귀의 인자로 주기 위해서 배열 깊은 복사
int[][] copy = new int[arr.length][arr[0].length];
for(int r=0; r<arr.length; r++)
System.arraycopy(arr[r], 0, copy[r], 0, arr[r].length);
// 현재 방향의 상하좌우 다 체크
for(int j=0; j<4; j++) {
// 실제로 배열을 돌리거나 할 필요없다. 그냥 통과 여부만 달리하면 됨.
// 따라서 돌렸다고 가정하면 이 방향으로 갈 수 있는지 확인하는 게 아래 코드!
if((CCTV[type] & 1<<(i+j)%4) == 0)
continue;
// j%4는 의미 없음.. 수정 전 코드의 잔재ㅠ
int r = cctv[idx][0] + dr[j%4];
int c = cctv[idx][1] + dc[j%4];
// 벽과 만날 때까지 계속 변경
while(copy[r][c]!=6) {
if(copy[r][c]==0) {
temp++; // 미감시구역이었다면 이제 감시구역이니 1+
copy[r][c] = 7; // 이미 감시구역임을 알리기 위해 7로 표시함
}
r += dr[j%4];
c += dc[j%4];
}
}
// 선택한 cctv 방향에 이어서 다음 cctv의 최적해 구해서 더하기
temp += monitoring(idx+1, cctv, copy);
// 최적해 구했으면 업데이트
if(max<temp) {
max = temp;
}
}
return max;
}소스코드
최종 제출한 코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int[] dr = {1, 0, -1, 0};
public static int[] dc = {0, -1, 0, 1};
public static int[] CCTV = {0b0000, 0b1000, 0b1010, 0b1001, 0b1011, 0b1111}; //CCTV별 탐색 비트마스크
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] arr = getArr(N, M); // 가장자리 벽을 세워 맵 만듦
int[][] cctv = new int[9][3]; // CCTV 정보 저장할 배열
int space = 0; // 미감시 구역
int idx = 0; // CCTV 개수
for(int n=1; n<=N; n++) {
st = new StringTokenizer(br.readLine());
for(int m=1; m<=M; m++) {
int temp = Integer.parseInt(st.nextToken());
arr[n][m] = temp; // 일단 저장
if(temp>0 && temp<=5) // CCTV면 CCTV 배열에 저장
cctv[idx++] = new int[] {n, m, temp};
else if(temp==0) // 미감시 구역 카운트
space++;
}
}
space -= monitoring(0, cctv, arr); // 전체 CCTV 가동하여 감시구역 제외하기
System.out.println(space); // 미감시 구역 개수 출력
}
private static int monitoring(int idx, int[][] cctv, int[][] arr) {
if(cctv[idx][0]==0) return 0; // CCTV 없으면 그냥 종료
int type = cctv[idx][2]; // CCTV 종류
int max = 0; // 최대 감시구역 개수
// cctv 회전
for(int i=0; i<4; i++) {
int temp = 0; // 해당 방향에서의 탐색 시작
int[][] copy = new int[arr.length][arr[0].length];
for(int r=0; r<arr.length; r++)
System.arraycopy(arr[r], 0, copy[r], 0, arr[r].length);
// 현재 방향의 상하좌우 다 체크
for(int j=0; j<4; j++) {
if((CCTV[type] & 1<<(i+j)%4) == 0)
continue;
int r = cctv[idx][0] + dr[j%4];
int c = cctv[idx][1] + dc[j%4];
while(copy[r][c]!=6) {
if(copy[r][c]==0) {
temp++;
copy[r][c] = 7;
}
r += dr[j%4];
c += dc[j%4];
}
}
temp += monitoring(idx+1, cctv, copy);
if(max<temp) {
max = temp;
}
}
return max;
}
private static int[][] getArr(int N, int M) {
int[][] arr = new int[N+2][M+2];
for(int n=0; n<N+2; n++) {
for(int m=0; m<M+2; m++) {
arr[n][m] = 6;
}
}
return arr;
}
}결과
제출 결과는 다음과 같았다.
고찰
범위도 대놓고 브루트포스하라고 정해놓은 것같은데 너무 이상한 곳에서 시간을 버린 것 같다. 더 나은 방법을 고려해보는 것은 좋은 시도이지만, 특히 빠르게 구현해야하는 코테 등에서는 일단 생각나는 방법으로 구현하고 개선해나가는 것이 더 나은 것 같다.
오엥