티스토리 뷰
728x90
문제
- 사무실에 총 K개의 CCTV가 설치되어 있음
- CCTV는 5가지 종류
- CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있음
- 사무실에 벽이 있는데 CCTV는 벽을 통과할 수 없음
- CCTV가 감시할 수 없는 영역은 사각지대
- CCTV는 회전할 수 있는데, 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 함
- 0은 빈칸, 6은 벽, 1~5는 CCTV를 나타냄
- CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하기
해결방법
처음에는 그리디 방식으로 각 CCTV에서 감시할 수 있는 최대의 칸을 감시할 수 있도록 코드를 작성하였다. 하지만, 더 나은 방법으로 감시할 수 있는 방향이 있었다. 예를 들어 (0, 0)부터 CCTV에서 최대의 칸을 감시하기를 시작했다면, (0, 5)에 있는 CCTV가 바라볼 수 있는 방향이 여러가지인데 최적의 방향을 찾아 최대로 감시하고 나중에 (3, 5)에 있는 CCTV가 감시할 수 있는 방향을 찾아야 하는데, 벽에 가려지고 감시할 수 있는 방향이 이미 감시되고 있는 방향이라면 추가로 더 감시할 수 있는 부분이 없어진다. 실제로는 나중에 나온 CCTV가 먼저 그 방향을 감시하고 이전에 나온 CCTV가 다른 방향으로 감시를 해야 더 적은 사각 지대를 만들 수 있는 것이다.
더보기
1) 틀린 코드 - 각 CCTV에서 감시할 수 있는 최대의 칸을 감시하도록 작성한 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M, result;
static int[][] room;
static boolean[][] cctv;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
result = N*M;
room = new int[N][M];
cctv = new boolean[N][M];
for(int i = 0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j<M; j++) {
room[i][j] = Integer.parseInt(st.nextToken());
if(room[i][j] != 0) result--;
}
}
for(int i = N-1; i>=0; i--) {
for(int j = M-1; j>=0; j--) {
if(room[i][j] != 0)
result -= checkCCTV(i, j, room[i][j]);
}
}
System.out.println(result);
}
// 각 위치에서 상우하좌 cctv 범위 구하기
// 상
static int checkTop(int i, int j, boolean check) {
int count = 0;
for(int top = i-1; top>=0; top--) {
if(room[top][j] == 6) return count;
if(room[top][j] != 0) continue;
if(!check) count++;
else {
count++;
room[top][j] = -1;
}
}
return count;
}
// 우
static int checkRight(int i, int j, boolean check) {
int count = 0;
for(int right = j+1; right<M; right++) {
if(room[i][right] == 6) return count;
if(room[i][right] != 0) continue;
if(!check) count++;
else {
count++;
room[i][right] = -1;
}
}
return count;
}
// 하
static int checkDown(int i, int j, boolean check) {
int count = 0;
for(int down = i+1; down<N; down++) {
if(room[down][j] == 6) return count;
if(room[down][j] != 0) continue;
if(!check) count++;
else {
count++;
room[down][j] = -1;
}
}
return count;
}
// 좌
static int checkLeft(int i, int j, boolean check) {
int count = 0;
for(int left = j-1; left>=0; left--) {
if(room[i][left] == 6) return count;
if(room[i][left] != 0) continue;
if(!check) count++;
else {
count++;
room[i][left] = -1;
}
}
return count;
}
static int checkCCTV(int i, int j, int CCTV) {
int max = 0;
int maxDirection = 0;
switch (CCTV) {
case 1:
// 상(0)
int top = checkTop(i, j, false);
if(max <= top) max = top;
// 우(1)
int right = checkRight(i, j, false);
if(max <= right){
max = right;
maxDirection = 1;
}
// 하(2)
int down = checkDown(i, j, false);
if(max <= down) {
max = down;
maxDirection = 2;
}
// 좌(3)
int left = checkLeft(i, j, false);
if(max <= left) {
max = left;
maxDirection = 3;
}
// 해당하는 부분 색칠
if(maxDirection == 0) checkTop(i, j, true);
else if(maxDirection == 1) checkRight(i, j, true);
else if(maxDirection == 2) checkDown(i, j, true);
else if(maxDirection == 3) checkLeft(i, j, true);
break;
case 2 :
// 상하(0)
top = checkTop(i, j, false);
down = checkDown(i, j, false);
if(max <= top+down) max = top + down;
// 좌우(1)
left = checkLeft(i, j, false);
right = checkRight(i, j, false);
if(max <= left + right) {
max = left + right;
maxDirection = 1;
}
// 해당하는 부분 색칠
if(maxDirection == 0) {
checkTop(i, j, true);
checkDown(i, j, true);
} else {
checkLeft(i, j, true);
checkRight(i, j, true);
}
break;
case 3 :
// 상우(0)
top = checkTop(i, j, false);
right = checkRight(i, j, false);
if(max <= top + right) max = top + right;
// 우하(1)
right = checkRight(i, j, false);
down = checkDown(i, j, false);
if(max <= right + down) {
max = right + down;
maxDirection = 1;
}
// 하좌(2)
down = checkDown(i, j, false);
left = checkLeft(i, j, false);
if(max <= down + left) {
max = down + left;
maxDirection = 2;
}
// 좌상(3)
left = checkLeft(i, j, false);
top = checkTop(i, j, false);
if(max <= left + top) {
max = left + top;
maxDirection = 3;
}
// 해당하는 부분 색칠
if(maxDirection == 0) {
checkTop(i, j, true);
checkRight(i, j, true);
} else if(maxDirection == 1) {
checkRight(i, j, true);
checkDown(i, j, true);
} else if(maxDirection == 2) {
checkDown(i, j, true);
checkLeft(i, j, true);
} else if(maxDirection == 3) {
checkLeft(i, j, true);
checkTop(i, j, true);
}
break;
case 4 :
// 좌우상(0)
left = checkLeft(i, j, false);
right = checkRight(i, j, false);
top = checkTop(i, j, false);
if(max <= left + right + top) max = left + right + top;
// 좌우하(1)
left = checkLeft(i, j, false);
right = checkRight(i, j, false);
down = checkDown(i, j, false);
if(max <= left + right + down) {
max = left + right + down;
maxDirection = 1;
}
// 상하우(2)
top = checkTop(i, j, false);
down = checkDown(i, j, false);
right = checkRight(i, j, false);
if(max <= top + down + right) {
max = top + down + right;
maxDirection = 2;
}
// 상하좌(3)
top = checkTop(i, j, false);
down = checkDown(i, j, false);
left = checkLeft(i, j, false);
if(max <= top + down + left) {
max = top + down + left;
maxDirection = 3;
}
// 해당하는 부분 색칠
if(maxDirection == 0) {
checkLeft(i, j, true);
checkRight(i, j, true);
checkTop(i, j, true);
} else if(maxDirection == 1) {
checkLeft(i, j, true);
checkRight(i, j, true);
checkDown(i, j, true);
} else if(maxDirection == 2) {
checkTop(i, j, true);
checkDown(i, j, true);
checkRight(i, j, true);
} else if(maxDirection == 3) {
checkTop(i, j, true);
checkDown(i, j, true);
checkLeft(i, j, true);
}
break;
case 5 :
max = checkTop(i, j, true)
+ checkDown(i, j, true)
+ checkLeft(i, j, true)
+ checkRight(i, j, true);
break;
case 6 :
max = 0;
break;
}
return max;
}
}위 방법으로 해결하지 못한 부분을 해결하기 위해 순열을 생각해보았다. 각 CCTV별로 바라볼 수 있는 방향의 경우에 따라 사각지대의 수가 달라지기 때문에 각 CCTV별 경우의 수 중에서 순열로 선택하고 그 경우에 따라 사각지대를 계산해보는 것이다.
1번 CCTV는 한 방향만을 감시하고 있기 때문에 (상, 우, 하, 좌) 4개의 방향 중 한 방향을 선택해서 감시해야 한다.
2번 CCTV는 양 방향을 감시하고 있기 때문에 (상하, 좌우) 2개의 방향 중 한 방향을 선택해서 감시해야 한다.
3번 CCTV는 90도로 감시하고 있기 때문에 (상우, 우하, 하좌, 좌상) 4개의 방향 중 한 방향을 선택해서 감시해야 한다.
4번 CCTV는 세 방향을 감시하고 있기 때문에 (좌상우, 상우하, 우하좌, 하좌상) 4개의 방향 중 한 방향을 선택해서 감시해야 한다.
5번 CCTV는 네 방향을 감시하고 있기 때문에 경우의 수는 1가지로 네 방향을 감시할 수 있다.
따라서 각 CCTV 정보가 주어졌을 때, 어떤 방향으로 선택할지를 경우의 수를 다 뽑아보고, 그 경우에 따라 사각지대를 구해 최소 값을 찾아낼 수 있도록 코드를 구성하였다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M, maxCCTV, result;
static int[] cctvDirCnt;
static int[][] room;
static boolean[][] cctv;
static List<CCTV> cctvList;
// CCTV class
static class CCTV {
int i;
int j;
int cctvNum;
public CCTV(int i, int j, int cctvNum) {
this.i = i;
this.j = j;
this.cctvNum = cctvNum;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
maxCCTV = Integer.MIN_VALUE; // CCTV가 감시할 수 있는 최대 범위
result = N*M; // 정답 저장 변수
room = new int[N][M];
cctv = new boolean[N][M];
cctvList = new ArrayList<>();
for(int i = 0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j<M; j++) {
room[i][j] = Integer.parseInt(st.nextToken());
if(room[i][j] != 0) {
result--; // CCTV가 위치하는 곳은 사각지대가 아님
// 벽을 제외하고 CCTV 정보로 등록
if(room[i][j] != 6) {
cctvList.add(new CCTV(i, j, room[i][j]));
}
}
}
}
cctvDirCnt = new int[cctvList.size()];
cctvDirection(0);
System.out.println(result-maxCCTV);
}
// 각 위치에서 상우하좌 cctv 범위 구하기
// 상
static int checkTop(int i, int j, boolean check) {
int count = 0;
for(int top = i-1; top>=0; top--) {
if(room[top][j] == 6) return count;
if(check) {
if(room[top][j] > 0) continue;
if(room[top][j] == 0) count++;
room[top][j] -= 1;
}
else {
count++;
if(room[top][j] < 0) room[top][j] += 1;
}
}
return count;
}
// 우
static int checkRight(int i, int j, boolean check) {
int count = 0;
for(int right = j+1; right<M; right++) {
if(room[i][right] == 6) return count;
if(check) {
if(room[i][right] > 0) continue;
if(room[i][right] == 0) count++;
room[i][right] -= 1;
}
else {
count++;
if(room[i][right] < 0) room[i][right] += 1;
}
}
return count;
}
// 하
static int checkDown(int i, int j, boolean check) {
int count = 0;
for(int down = i+1; down<N; down++) {
if(room[down][j] == 6) return count;
if(check) {
if(room[down][j] > 0) continue;
if(room[down][j] == 0)count++;
room[down][j] -= 1;
}
else {
count++;
if(room[down][j] < 0) room[down][j] += 1;
}
}
return count;
}
// 좌
static int checkLeft(int i, int j, boolean check) {
int count = 0;
for(int left = j-1; left>=0; left--) {
if(room[i][left] == 6) return count;
if(check) {
if(room[i][left] > 0) continue;
if(room[i][left] == 0) count++;
room[i][left] -= 1;
}
else {
count++;
if(room[i][left] < 0) room[i][left] += 1;
}
}
return count;
}
// CCTV 방향 순열로 선택 후 감시 영역 파악하는 함수
static void cctvDirection(int cnt) {
// CCTV 방향을 모두 선택했다면
if(cnt == cctvList.size()) {
int sum = 0;
// 감시 영역 파악
for(int i = 0; i<cctvList.size(); i++) {
sum += cctvDirCnt[i];
}
// 감시 영역이 최대가 되어야 사각지대가 최소가 됨
maxCCTV = Math.max(maxCCTV, sum);
return;
}
// CCTV 번호에 따라서 감시할 수 있는 방향의 경우의 수가 다름
switch (cctvList.get(cnt).cctvNum) {
// CCTV 1번
case 1:
// 상 우 하 좌 4가지의 경우의 수 (순열)
for(int i = 0; i<4; i++) {
// 뽑았을 때 확인 후
if(i == 0) cctvDirCnt[cnt] = checkTop(cctvList.get(cnt).i, cctvList.get(cnt).j, true);
else if(i == 1) cctvDirCnt[cnt] = checkRight(cctvList.get(cnt).i, cctvList.get(cnt).j, true);
else if(i == 2) cctvDirCnt[cnt] = checkDown(cctvList.get(cnt).i, cctvList.get(cnt).j, true);
else if(i == 3) cctvDirCnt[cnt] = checkLeft(cctvList.get(cnt).i, cctvList.get(cnt).j, true);
// 이후 과정 진행
cctvDirection(cnt+1);
// 다른 방향을 선택하기 위해 뽑았던 것 되돌리기
if(i == 0) checkTop(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
else if(i == 1) checkRight(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
else if(i == 2) checkDown(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
else if(i == 3) checkLeft(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
}
break;
// CCTV 2번
case 2:
// 상하 좌우 2가지의 경우의 수 (순열)
for(int i = 0; i<2; i++) {
// 뽑았을 때 확인 후
if(i == 0) {
cctvDirCnt[cnt] = checkTop(cctvList.get(cnt).i, cctvList.get(cnt).j, true)
+ checkDown(cctvList.get(cnt).i, cctvList.get(cnt).j, true);
}
else if(i == 1) {
cctvDirCnt[cnt] = checkLeft(cctvList.get(cnt).i, cctvList.get(cnt).j, true)
+ checkRight(cctvList.get(cnt).i, cctvList.get(cnt).j, true);
}
// 이후 과정 진행
cctvDirection(cnt+1);
// 다른 방향을 선택하기 위해 뽑았던 것 되돌리기
if(i == 0) {
checkTop(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
checkDown(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
}
else if(i == 1) {
checkLeft(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
checkRight(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
}
}
break;
// CCTV 3번
case 3:
// 상우 우하 하좌 좌상 4가지의 경우의 수 (순열)
for(int i = 0; i<4; i++) {
// 뽑았을 때 확인 후
if(i == 0) {
cctvDirCnt[cnt] = checkTop(cctvList.get(cnt).i, cctvList.get(cnt).j, true)
+ checkRight(cctvList.get(cnt).i, cctvList.get(cnt).j, true);
}
else if(i == 1) {
cctvDirCnt[cnt] = checkRight(cctvList.get(cnt).i, cctvList.get(cnt).j, true)
+ checkDown(cctvList.get(cnt).i, cctvList.get(cnt).j, true);
}
else if(i == 2) {
cctvDirCnt[cnt] = checkDown(cctvList.get(cnt).i, cctvList.get(cnt).j, true)
+ checkLeft(cctvList.get(cnt).i, cctvList.get(cnt).j, true);
}
else if(i == 3) {
cctvDirCnt[cnt] = checkLeft(cctvList.get(cnt).i, cctvList.get(cnt).j, true)
+ checkTop(cctvList.get(cnt).i, cctvList.get(cnt).j, true);
}
// 이후 과정 진행
cctvDirection(cnt+1);
// 다른 방향을 선택하기 위해 뽑았던 것 되돌리기
if(i == 0) {
checkTop(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
checkRight(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
}
else if(i == 1) {
checkRight(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
checkDown(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
}
else if(i == 2) {
checkDown(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
checkLeft(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
}
else if(i == 3) {
checkLeft(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
checkTop(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
}
}
break;
// CCTV 4번
case 4:
// 좌상우 상우하 우하좌 하좌상 4가지의 경우의 수 (순열)
for(int i = 0; i<4; i++) {
// 뽑았을 때 확인 후
if(i == 0) {
cctvDirCnt[cnt] = checkLeft(cctvList.get(cnt).i, cctvList.get(cnt).j, true)
+ checkTop(cctvList.get(cnt).i, cctvList.get(cnt).j, true)
+ checkRight(cctvList.get(cnt).i, cctvList.get(cnt).j, true);
}
else if(i == 1) {
cctvDirCnt[cnt] = checkTop(cctvList.get(cnt).i, cctvList.get(cnt).j, true)
+ checkRight(cctvList.get(cnt).i, cctvList.get(cnt).j, true)
+ checkDown(cctvList.get(cnt).i, cctvList.get(cnt).j, true);
}
else if(i == 2) {
cctvDirCnt[cnt] = checkRight(cctvList.get(cnt).i, cctvList.get(cnt).j, true)
+ checkDown(cctvList.get(cnt).i, cctvList.get(cnt).j, true)
+ checkLeft(cctvList.get(cnt).i, cctvList.get(cnt).j, true);
}
else if(i == 3) {
cctvDirCnt[cnt] = checkDown(cctvList.get(cnt).i, cctvList.get(cnt).j, true)
+ checkLeft(cctvList.get(cnt).i, cctvList.get(cnt).j, true)
+ checkTop(cctvList.get(cnt).i, cctvList.get(cnt).j, true);
}
// 이후 과정 진행
cctvDirection(cnt+1);
// 다른 방향을 선택하기 위해 뽑았던 것 되돌리기
if(i == 0) {
checkLeft(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
checkTop(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
checkRight(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
}
else if(i == 1) {
checkTop(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
checkRight(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
checkDown(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
}
else if(i == 2) {
checkRight(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
checkDown(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
checkLeft(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
}
else if(i == 3) {
checkDown(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
checkLeft(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
checkTop(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
}
}
break;
// CCTV 5번
case 5:
// 상우하좌 1가지의 경우의 수 뽑았을 때 확인 후
cctvDirCnt[cnt] = checkTop(cctvList.get(cnt).i, cctvList.get(cnt).j, true)
+ checkRight(cctvList.get(cnt).i, cctvList.get(cnt).j, true)
+ checkDown(cctvList.get(cnt).i, cctvList.get(cnt).j, true)
+ checkLeft(cctvList.get(cnt).i, cctvList.get(cnt).j, true);
// 이후 과정 진행
cctvDirection(cnt+1);
// 다른 방향을 선택하기 위해 뽑았던 것 되돌리기
checkTop(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
checkRight(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
checkDown(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
checkLeft(cctvList.get(cnt).i, cctvList.get(cnt).j, false);
break;
}
}
}728x90
'Algorithm > Baekjoon' 카테고리의 다른 글
| [백준] 11779번 최소비용 구하기 2 (JAVA) (0) | 2023.03.02 |
|---|---|
| [백준] 1753번 최단경로 (JAVA) (0) | 2023.03.02 |
| [백준] 9205번 맥주 마시면서 걸어가기 (JAVA) (0) | 2023.02.28 |
| [백준] 5427번 불 (JAVA) (0) | 2023.02.27 |
| [백준] 1926번 그림 (JAVA) (0) | 2023.02.27 |
댓글