1. 문제 링크
https://www.acmicpc.net/problem/15683
2. 문제
요약
- 스타트링크의 사무실은 1x1 크기의 정사각형으로 나누어져 있는 NxM 크기의 직사각형으로 나타낼 수 있고 사무실에는 총 K개의 CCTV가 설치되어 있습니다.
- CCTV는 5가지 종류가 있고 각 CCTV가 감시할 수 있는 방법은 다음과 같습니다.
- 1번 CCTV는 한 쪽 방향만 감시할 수 있습니다.
- 2번 CCTV는 두 방향을 감시할 수 있는데, 감시하는 방향이 서로 반대방향입니다.
- 3번 CCTV는 두 방향을 감시할 수 있는데, 감시하는 방향이 직각 방향입니다.
- 4번 CCTV는 세 방향을 감시할 수 있습니다.
- 5번 CCTV는 네 방향을 감시할 수 있습니다.
- CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있지만 사무실에는 벽이 있는데 CCTV는 벽을 통과할 수 없습니다.
- CCTV가 감시할 수 없는 영역은 사각지대라고 합니다.
- CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려는 방향이 가로 또는 세로 방향이어야 합니다.
- 사무실의 크기와 상태, CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서 사각 지대의 최소 크기를 구하는 문제입니다.
- 사무실의 상태가 값들로 표현되는데, 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호입니다.
- 입력: 첫 번째 줄에 1보다 크거나 같고 8보다 작거나 같은 사무실의 세로 크기 N, 가로 크기 M이 주어지고 두 번째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어집니다.
- CCTV의 최대 개수는 8개를 넘지 않습니다.
- 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타냅니다.
- 출력: 첫째 줄에 사각 지대의 최소 크기를 출력합니다.
3. 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static int[][] map;
static int[][] cnt;
static ArrayList<Point> CCTVs;
static int min = Integer.MAX_VALUE;
static void input() {
Reader scanner = new Reader();
N = scanner.nextInt();
M = scanner.nextInt();
map = new int[N][M];
cnt = new int[N][M];
CCTVs = new ArrayList<>();
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
map[i][j] = scanner.nextInt();
if(map[i][j] != 0 && map[i][j] != 6) CCTVs.add(new Point(i, j));
}
}
}
static void solution(int idx) {
if(idx == CCTVs.size()) {
min = Math.min(min, getBlindSpotNum());
return;
}
// 1: 오른쪽, 2: 아래, 3: 왼쪽, 4: 위
for(int j = 1; j <= 4; j++) {
Point cctv = CCTVs.get(idx);
switch(map[cctv.x][cctv.y]) {
case 1:
if(j == 1) {
fillRight(cctv, -1);
solution(idx + 1);
fillRight(cctv, 0);
} else if(j == 2) {
fillDown(cctv, -1);
solution(idx + 1);
fillDown(cctv, 0);
} else if(j == 3) {
fillLeft(cctv, -1);
solution(idx + 1);
fillLeft(cctv, 0);
} else if(j == 4) {
fillUp(cctv, -1);
solution(idx + 1);
fillUp(cctv, 0);
}
break;
case 2:
if(j == 1 || j == 3) {
fillRight(cctv, -1);
fillLeft(cctv, -1);
solution(idx + 1);
fillRight(cctv, 0);
fillLeft(cctv, 0);
} else if(j == 2 || j == 4) {
fillUp(cctv, -1);
fillDown(cctv, -1);
solution(idx + 1);
fillDown(cctv, 0);
fillUp(cctv, 0);
}
break;
case 3:
if(j == 1) {
fillRight(cctv, -1);
fillUp(cctv, -1);
solution(idx + 1);
fillRight(cctv, 0);
fillUp(cctv, 0);
} else if(j == 2) {
fillRight(cctv, -1);
fillDown(cctv, -1);
solution(idx + 1);
fillRight(cctv, 0);
fillDown(cctv, 0);
} else if(j == 3) {
fillLeft(cctv, -1);
fillDown(cctv, -1);
solution(idx + 1);
fillLeft(cctv, 0);
fillDown(cctv, 0);
} else if(j == 4) {
fillLeft(cctv, -1);
fillUp(cctv, -1);
solution(idx + 1);
fillLeft(cctv, 0);
fillUp(cctv, 0);
}
break;
case 4:
if(j == 1) {
fillRight(cctv, -1);
fillUp(cctv, -1);
fillLeft(cctv, -1);
solution(idx + 1);
fillRight(cctv, 0);
fillUp(cctv, 0);
fillLeft(cctv, 0);
} else if(j == 2) {
fillRight(cctv, -1);
fillUp(cctv, -1);
fillDown(cctv, -1);
solution(idx + 1);
fillRight(cctv, 0);
fillUp(cctv, 0);
fillDown(cctv, 0);
} else if(j == 3) {
fillRight(cctv, -1);
fillDown(cctv, -1);
fillLeft(cctv, -1);
solution(idx + 1);
fillRight(cctv, 0);
fillDown(cctv, 0);
fillLeft(cctv, 0);
} else if(j == 4) {
fillDown(cctv, -1);
fillUp(cctv, -1);
fillLeft(cctv, -1);
solution(idx + 1);
fillDown(cctv, 0);
fillUp(cctv, 0);
fillLeft(cctv, 0);
}
break;
case 5:
fillRight(cctv, -1);
fillUp(cctv, -1);
fillDown(cctv, -1);
fillLeft(cctv, -1);
solution(idx + 1);
fillRight(cctv, 0);
fillUp(cctv, 0);
fillDown(cctv, 0);
fillLeft(cctv, 0);
break;
default:
break;
}
}
}
static void fillRight(Point p, int type) {
if(type != 0) {
for(int i = p.y + 1; i < M; i++) {
if(map[p.x][i] == 0 || map[p.x][i] == -1) {
cnt[p.x][i]++;
map[p.x][i] = type;
}
else if(map[p.x][i] == 6) break;
}
} else {
for(int i = p.y + 1; i < M; i++) {
if(map[p.x][i] == -1) {
cnt[p.x][i]--;
if(cnt[p.x][i] == 0) map[p.x][i] = type;
}
else if(map[p.x][i] == 6) break;
}
}
}
static void fillLeft(Point p, int type) {
if(type != 0) {
for(int i = p.y - 1; i >= 0; i--) {
if(map[p.x][i] == 0 || map[p.x][i] == -1) {
cnt[p.x][i]++;
map[p.x][i] = type;
}
else if(map[p.x][i] == 6) break;
}
} else {
for(int i = p.y - 1; i >= 0; i--) {
if(map[p.x][i] == -1) {
cnt[p.x][i]--;
if(cnt[p.x][i] == 0) map[p.x][i] = type;
}
else if(map[p.x][i] == 6) break;
}
}
}
static void fillUp(Point p, int type) {
if(type != 0) {
for(int i = p.x - 1; i >= 0; i--) {
if(map[i][p.y] == 0 || map[i][p.y] == -1) {
cnt[i][p.y]++;
map[i][p.y] = type;
}
else if(map[i][p.y] == 6) break;
}
} else {
for(int i = p.x - 1; i >= 0; i--) {
if(map[i][p.y] == -1) {
cnt[i][p.y]--;
if(cnt[i][p.y] == 0) map[i][p.y] = type;
}
else if(map[i][p.y] == 6) break;
}
}
}
static void fillDown(Point p, int type) {
if(type != 0) {
for(int i = p.x + 1; i < N; i++) {
if(map[i][p.y] == 0 || map[i][p.y] == -1) {
cnt[i][p.y]++;
map[i][p.y] = type;
}
else if(map[i][p.y] == 6) break;
}
} else {
for(int i = p.x + 1; i < N; i++) {
if(map[i][p.y] == -1) {
cnt[i][p.y]--;
if(cnt[i][p.y] == 0) map[i][p.y] = type;
}
else if(map[i][p.y] == 6) break;
}
}
}
static int getBlindSpotNum() {
int sum = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(map[i][j] == 0) sum++;
}
}
return sum;
}
public static void main(String[] args) {
input();
solution(0);
System.out.println(min);
}
static class Reader {
BufferedReader br;
StringTokenizer st;
public Reader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while(st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
static class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}4. 접근
- 모든 카메라에 대해서 90도씩 회전을 시켜보고 그 모든 경우 중에서 사각 지대가 최소가 되는 경우를 선택한 후에 그 때의 사각 지대 크기를 출력합니다.
- 사무실 정보를 입력받을 때 카메라가 있는 위치는 CCTVs라는 ArrayList에 넣어줍니다.
- 이후 각 CCTV를 회전시켜볼 때, CCTVs에 있는 위치들을 이용합니다.
solution 함수
static void solution(int idx) {
if(idx == CCTVs.size()) {
min = Math.min(min, getBlindSpotNum());
return;
}
// 1: 오른쪽, 2: 아래, 3: 왼쪽, 4: 위
for(int j = 1; j <= 4; j++) {
Point cctv = CCTVs.get(idx);
switch(map[cctv.x][cctv.y]) {
case 1:
if(j == 1) {
fillRight(cctv, -1);
solution(idx + 1);
fillRight(cctv, 0);
} else if(j == 2) {
fillDown(cctv, -1);
solution(idx + 1);
fillDown(cctv, 0);
} else if(j == 3) {
fillLeft(cctv, -1);
solution(idx + 1);
fillLeft(cctv, 0);
} else if(j == 4) {
fillUp(cctv, -1);
solution(idx + 1);
fillUp(cctv, 0);
}
break;
case 2:
if(j == 1 || j == 3) {
fillRight(cctv, -1);
fillLeft(cctv, -1);
solution(idx + 1);
fillRight(cctv, 0);
fillLeft(cctv, 0);
} else if(j == 2 || j == 4) {
fillUp(cctv, -1);
fillDown(cctv, -1);
solution(idx + 1);
fillDown(cctv, 0);
fillUp(cctv, 0);
}
break;
case 3:
if(j == 1) {
fillRight(cctv, -1);
fillUp(cctv, -1);
solution(idx + 1);
fillRight(cctv, 0);
fillUp(cctv, 0);
} else if(j == 2) {
fillRight(cctv, -1);
fillDown(cctv, -1);
solution(idx + 1);
fillRight(cctv, 0);
fillDown(cctv, 0);
} else if(j == 3) {
fillLeft(cctv, -1);
fillDown(cctv, -1);
solution(idx + 1);
fillLeft(cctv, 0);
fillDown(cctv, 0);
} else if(j == 4) {
fillLeft(cctv, -1);
fillUp(cctv, -1);
solution(idx + 1);
fillLeft(cctv, 0);
fillUp(cctv, 0);
}
break;
case 4:
if(j == 1) {
fillRight(cctv, -1);
fillUp(cctv, -1);
fillLeft(cctv, -1);
solution(idx + 1);
fillRight(cctv, 0);
fillUp(cctv, 0);
fillLeft(cctv, 0);
} else if(j == 2) {
fillRight(cctv, -1);
fillUp(cctv, -1);
fillDown(cctv, -1);
solution(idx + 1);
fillRight(cctv, 0);
fillUp(cctv, 0);
fillDown(cctv, 0);
} else if(j == 3) {
fillRight(cctv, -1);
fillDown(cctv, -1);
fillLeft(cctv, -1);
solution(idx + 1);
fillRight(cctv, 0);
fillDown(cctv, 0);
fillLeft(cctv, 0);
} else if(j == 4) {
fillDown(cctv, -1);
fillUp(cctv, -1);
fillLeft(cctv, -1);
solution(idx + 1);
fillDown(cctv, 0);
fillUp(cctv, 0);
fillLeft(cctv, 0);
}
break;
case 5:
fillRight(cctv, -1);
fillUp(cctv, -1);
fillDown(cctv, -1);
fillLeft(cctv, -1);
solution(idx + 1);
fillRight(cctv, 0);
fillUp(cctv, 0);
fillDown(cctv, 0);
fillLeft(cctv, 0);
break;
default:
break;
}
}
}- solution 함수에서는 각 CCTV를 90도씩 회전시켜보면서 각 경우에서 사각 지대의 크기를 구한 후에 사각 지대의 최소 크기를 나타내는 변수 min 값을 갱신시킵니다.
- 이 함수는 매개변수를 하나 갖는데, idx 매개변수는 현재 회전시키려고 하는 CCTV 위치의 index를 나타냅니다.
- 그렇기 때문에 idx가 CCTVs의 크기와 같아진다면 모든 CCTV에 대해서 회전시켜본 것이므로 이 때 getBlindSpotNum() 함수를 통해 사각 지대의 크기를 구하고 min 값을 갱신시킵니다.
- CCTV가 바라볼 수 있는 방향이 네 방향이기 때문에 오른쪽 방향을 1, 아래 방향을 2, 왼쪽 방향을 3, 위 방향을 4로 설정하고 CCTV들을 각각 이 네 방향으로 회전시켜봅니다.
- CCTV를 회전시킨 후에는 fill류 함수들을 통해 각 방향에서 CCTV가 감시할 수 있는 위치들을 찾습니다.
- 모든 CCTV들을 다 회전시켜봤다면 이전으로 돌아가 다른 방향으로 CCTV를 회전시켜봅니다.
- 이러한 방식으로 CCTV를 회전시킬 수 있는 모든 경우를 진행합니다.
fill~ 함수
static void fillRight(Point p, int type) {
if(type != 0) {
for(int i = p.y + 1; i < M; i++) {
if(map[p.x][i] == 0 || map[p.x][i] == -1) {
cnt[p.x][i]++;
map[p.x][i] = type;
}
else if(map[p.x][i] == 6) break;
}
} else {
for(int i = p.y + 1; i < M; i++) {
if(map[p.x][i] == -1) {
cnt[p.x][i]--;
if(cnt[p.x][i] == 0) map[p.x][i] = type;
}
else if(map[p.x][i] == 6) break;
}
}
}- fill류 함수는 CCTV가 해당 방향을 바라볼 때, 해당 CCTV가 감시할 수 있는 위치를 찾는 함수입니다.
- 이 함수들은 두 개의 매개변수를 갖는데, p 매개변수는 CCTV의 위치를 나타내고, type 매개변수는 해당 CCTV가 감시할 수 있는 위치를 찾으려 한다면 -1 값을, 다른 경우를 보기 위해 CCTV가 감시할 수 있는 위치를 다시 감시할 수 없는 위치로 돌리려고 한다면 0 값을 받습니다.
- 돌아가는 로직은 같기 때문에 CCTV가 오른쪽 방향을 감시하는 경우인 fillRight 함수를 예로 하여 해당 함수를 보겠습니다.
- 만약 type이 0이 아니라면
- 현재 CCTV가 있는 위치보다 한 칸 오른쪽 위치부터 같은 x좌표에서의 사무실 마지막 위치까지 각 위치에 대해서 각 위치의 값이 0이거나 -1이라면 해당 위치는 CCTV가 감시할 수 있는 곳이므로 그 위치의 값을 전달받은 type 값으로 변경하고 그 위치의 cnt 값을 1 증가시킵니다.
- 2차원 배열 cnt는 각 위치를 몇 대의 CCTV가 감시하고 있는지 나타내는 배열입니다.
- 만약 각 위치의 값이 6이라면 해당 위치는 벽이기 때문에 CCTV가 통과할 수 없어 이후 위치들은 확인하지 않고 함수를 끝냅니다.
- 만약 type이 0이라면
- 현재 CCTV가 있는 위치보다 한 칸 오른쪽 위치부터 같은 x좌표에서의 사무실 마지막 위치까지 각 위치에 대해서 각 위치의 값이 -1이라면 해당 위치는 CCTV가 감시하고 있는 곳이므로 다시 감시할 수 없는 곳으로 돌리기 위해 그 위치의 값을 0으로 변경하고 그 위치의 cnt 값을 1 감소시킵니다.
- 만약 각 위치의 값이 6이라면 벽이기 때문에 CCTV가 통과할 수 없어 이후 위치들은 CCTV가 감시할 수 없는 곳이기 때문에 이후 위치들은 확인하지 않고 함수를 끝냅니다.
getBlindSpotNum 함수
static int getBlindSpotNum() {
int sum = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(map[i][j] == 0) sum++;
}
}
return sum;
}- 이 함수는 각 경우에서 사각 지대의 크기를 구하는 함수입니다.
- 사무실의 모든 위치를 확인하여 값이 0인 곳, 즉 CCTV가 감시하지 못하는 곳을 찾고 그러한 위치를 찾을 때마다 사각 지대의 크기를 뜻하는 변수 sum의 값을 1 증가시킵니다.
- 모든 위치에 대해서 확인했다면 sum을 반환하여 min을 갱신시키는 데에 사용합니다.
자바, 웹 개발을 열심히 공부하고 있습니다!