안녕하세요!
이번 포스팅은 백준의 감시 문제를 적어보겠습니다.
문제
요약
총 5개의 CCTV가 맵에 주어집니다.
각 CCTV는 감시할 수 있는 방향이 모두 제각각이며, 다른 CCTV 영역은 투과해서 감시할 수 있습니다.
하지만 벽(6)은 통과할 수 없습니다.
CCTV가 감시할 수 없는 사각지대의 영역 수를 리턴하는 문제입니다.
처음 생각한 방법
우선 5개의 CCTV를 어떻게 처리할까 고민했습니다.
CCTV 관리를 3차원 배열로 관리하고, 방향을 지정해서 처리했습니다.
그 후에 입력으로 들어오는0(빈 공간)을
이 문제는 시뮬레이션 문제이기 때문에 단계별로 처리만 잘 해준다면, 바로 통과할 수 있는 문제입니다 :)
코드 설명
static int R, C, SIZE, min, cctv[][][];
static char map[][];
static List<Integer> cctvList; // 맵에 존재하는 CCTV
static List<int[]> cctvLoc; // cctvList와 인덱스를 동일하게 가져가며, CCTV의 위치를 저장
// 상 하 좌 우
static int[] dr = { -1, 1, 0, 0 };
static int[] dc = { 0, 0, -1, 1 };Main 클래스에 선언한 클래스 변수들입니다.
입력값으로 받는 R, C, map 과 같은 것들을 선언하고
CCTV가 들어왔을 때 해당 CCTV의 위치를 저장하는 리스트를 함께 선언했습니다.
CCTV의 개수는 따로 입력으로 들어오지 않기 때문에 크기가 유동적인 리스트를 사용했고, 사방의 방향을 나타내는 dr, dc 배열도 선언해줍니다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());입력이 배열로 들어오기 때문에 버퍼를 사용해서 입력값을 받아줍니다.
private static void main(String[] args) {
// ...
cctvInit();
// ...
}
// cctv의 번호마다 가능한 방향 인덱스를 저장함
private static void cctvInit() {
cctv = new int[6][][];
cctv[1] = new int[][]{ {0}, {1}, {2}, {3} };
cctv[2] = new int[][]{ {0, 1}, {2, 3} };
cctv[3] = new int[][]{ {0, 2}, {0, 3}, {1, 2}, {1, 3} };
cctv[4] = new int[][]{ {0, 1, 2}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3} };
cctv[5] = new int[][]{ {0, 1, 2, 3} };
}그 이후에는 각 번호마다 CCTV를 방향에 맞도록 3차원 배열을 초기화해줍니다.
CCTV를 90도 회전할 수 있어서 가능한 모든 방향을 저장해줬습니다.
map = new char[R][C];
cctvList = new ArrayList<>();
cctvLoc = new ArrayList<>();
// 맵 초기화 & 사각지대 체크 & cctv 좌표, 번호 저장
for (int i = 0; i < R; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < C; j++) {
char c = st.nextToken().charAt(0);
if (c == '0') min++;
else if (c != '6'){
cctvList.add(Character.getNumericValue(c)); // 몇 번 CCTV인지 저장
cctvLoc.add(new int[]{i, j}); // 해당 CCTV의 좌표 저장
}
map[i][j] = c;
}
}map 배열을 RXC 크기로 초기화한 후에 입력값을 받아서 저장합니다.
만약 0 이 들어왔다면 빈 공간이므로 min 변수에 추가해줍니다.
벽을 나타내는 6 이 아니라면 CCTV 위치와 몇번 CCTV인지 저장해준 후 map 에 추가합니다.
SIZE = cctvList.size(); // 재귀 기저조건인 SIZE 저장
watch(0, min, map);입력값을 모두 처리한 후에는 모든 CCTV의 경우의 수를 판단하는 watch 메소드를 호출합니다.
private static void watch(int no, int cnt, char[][] currMap) {
// 만약 CCTV SIZE만큼 확인하거나 빈 공간이 이미 없을 때 return
if (no == SIZE || cnt == 0) {
min = Math.min(cnt, min);
return;
}
// 해당 CCTV가 위치한 좌표 (r,c)
int r = cctvLoc.get(no)[0];
int c = cctvLoc.get(no)[1];
int[][] currCCTV = cctv[cctvList.get(no)]; // 해당 번호의 CCTV가 확인할 수 있는 방향을 가져옴
// 방향이 여러개가 가능하면 하나씩 체크
for (int i = 0; i < currCCTV.length; i++) {
// 해당 CCTV가 감시한 영역을 체크할 배열 하나 더 선언 후 currMap 값을 copy
char[][] temp = new char[R][C];
for (int j = 0; j < R; j++) {
System.arraycopy(currMap[j], 0, temp[j], 0, C);
}
int sum = 0; // 감시할 수 있는 영역들의 합
// 방향을 차례로 체크하면서 감시 가능한 모든 영역을 표시
for (int j = 0; j < currCCTV[i].length; j++) {
int d = currCCTV[i][j]; // 체크할 방향
int nr = r + dr[d]; // next r
int nc = c + dc[d]; // next c
// 해당 좌표가 유효하고, 벽이 아니면 계속 반복 수행
while (isValid(nr, nc) && temp[nr][nc] != '6') {
// 만약 CCTV라면 continue
if (temp[nr][nc] != '0' && temp[nr][nc] != '#') {
nr += dr[d];
nc += dc[d];
continue;
}
// 빈 공간이라면 sum - 1
// #은 건너뜀
if (temp[nr][nc] == '0') {
sum++;
}
temp[nr][nc] = '#';
nr += dr[d];
nc += dc[d];
}
}
// 다음 CCTV 재귀호출
watch(no+1, cnt-sum, temp);
}
}watch 메소드는 감시할 수 있는 모든 위치에 # 을 체크한 후 재귀호출하는 메소드입니다.
no 는 체크할 CCTV 번호, cnt 는 현재까지의 빈 공간, currMap 은 재귀를 호출하면서 변경된 현 상태의 map 입니다.
클래스 변수로 원래 map 이 존재하기 때문에, 매개변수로 배열을 전달하며 배열을 다시 되돌려놓는 일을 줄여줬습니다.
(아래에서 메소드에 대해 더 자세하게 보겠습니다)
// 만약 CCTV SIZE만큼 확인하거나 빈 공간이 이미 없을 때 return
if (no == SIZE || cnt == 0) {
min = Math.min(cnt, min);
return;
}재귀 함수는 CCTV 개수만큼 호출되었거나(모든 CCTV를 고려했거나), 빈 공간이 존재하지 않을 때 종료합니다.
// 해당 CCTV가 위치한 좌표 (r,c)
int r = cctvLoc.get(no)[0];
int c = cctvLoc.get(no)[1];
int[][] currCCTV = cctv[cctvList.get(no)]; // 해당 번호의 CCTV가 확인할 수 있는 방향을 가져옴기저 조건에 해당하지 않는다면 현재 매개변수로 들어온 CCTV가 위치한 좌표를 가져오고, 현재 CCTV가 확인할 수 있는 방향을 가져옵니다.
// 방향이 여러개가 가능하면 하나씩 체크
for (int i = 0; i < currCCTV.length; i++) {
// 해당 CCTV가 감시한 영역을 체크할 배열 하나 더 선언 후 currMap 값을 copy
char[][] temp = new char[R][C];
for (int j = 0; j < R; j++) {
System.arraycopy(currMap[j], 0, temp[j], 0, C);
}
int sum = 0; // 감시할 수 있는 영역들의 합
// 방향을 차례로 체크하면서 감시 가능한 모든 영역을 표시
for (int j = 0; j < currCCTV[i].length; j++) {
int d = currCCTV[i][j]; // 체크할 방향
int nr = r + dr[d]; // next r
int nc = c + dc[d]; // next c
// 해당 좌표가 유효하고, 벽이 아니면 계속 반복 수행
while (isValid(nr, nc) && temp[nr][nc] != '6') {
// 만약 CCTV라면 continue
if (temp[nr][nc] != '0' && temp[nr][nc] != '#') {
nr += dr[d];
nc += dc[d];
continue;
}
// 빈 공간이라면 sum - 1
// #은 건너뜀
if (temp[nr][nc] == '0') {
sum++;
}
temp[nr][nc] = '#';
nr += dr[d];
nc += dc[d];
}
}
// 다음 CCTV 재귀호출
watch(no+1, cnt-sum, temp);
}현재 CCTV가 가능한 방향을 모두 체크해야 하므로 currCCTV.length 만큼 for문을 순회합니다.
CCTV가 감시하는 방향을 체크할 때는 배열이 바뀌어야 하므로 temp 배열을 선언해 매개변수로 들어온 currMap 배열을 복사해줍니다.
감시 가능한 방향을 차례로 체크하면서 감시 가능한 모든 영역을 # 로 표시합니다.
6 이 아니고, 0 과 # 모두 아니라면 CCTV 영역이므로 표시하지 않고 반복문을 continue 합니다.
위의 경우가 아니라면 빈 공간이므로 감시 가능하다는 표시인 # 를 표시한 후 sum++ 처리해줍니다.
현재 CCTV의 가능한 방향을 모두 체크했다면 watch 를 재귀호출해 모든 경우를 완전 탐색 합니다.
// 좌표의 유효성을 체크하는 메소드
private static boolean isValid(int r, int c) {
if (r<0 || r>=R || c<0 || c>=C) return false;
return true;
}map 을 빠져나갔는지 좌표의 유효성을 확인하는 메소드는 위와 같이 간단합니다.
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static int R, C, SIZE, min, cctv[][][];
static char map[][];
static List<Integer> cctvList; // 맵에 존재하는 CCTV
static List<int[]> cctvLoc; // cctvList와 인덱스를 동일하게 가져가며, CCTV의 위치를 저장
// 상 하 좌 우
static int[] dr = { -1, 1, 0, 0 };
static int[] dc = { 0, 0, -1, 1 };
public static void main(String[] args) throws IOException {
// 입력이 배열이므로 BufferedReader 사용
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
cctvInit(); // 각 CCTV가 감시할 수 있는 방향을 저장하는 cctv 배열을 초기화
map = new char[R][C];
cctvList = new ArrayList<>();
cctvLoc = new ArrayList<>();
// 맵 초기화 & 사각지대 체크 & cctv 좌표, 번호 저장
for (int i = 0; i < R; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < C; j++) {
char c = st.nextToken().charAt(0);
if (c == '0') min++;
else if (c != '6'){
cctvList.add(Character.getNumericValue(c)); // 몇 번 CCTV인지 저장
cctvLoc.add(new int[]{i, j}); // 해당 CCTV의 좌표 저장
}
map[i][j] = c;
}
}
SIZE = cctvList.size(); // 재귀 기저조건인 SIZE 저장
watch(0, min, map);
System.out.println(min);
}
// 감시할 수 있는 위치에 # 체크 후 재귀
private static void watch(int no, int cnt, char[][] currMap) {
// 만약 CCTV SIZE만큼 확인하거나 빈 공간이 이미 없을 때 return
if (no == SIZE || cnt == 0) {
min = Math.min(cnt, min);
return;
}
// 해당 CCTV가 위치한 좌표 (r,c)
int r = cctvLoc.get(no)[0];
int c = cctvLoc.get(no)[1];
int[][] currCCTV = cctv[cctvList.get(no)]; // 해당 번호의 CCTV가 확인할 수 있는 방향을 가져옴
// 방향이 여러개가 가능하면 하나씩 체크
for (int i = 0; i < currCCTV.length; i++) {
// 해당 CCTV가 감시한 영역을 체크할 배열 하나 더 선언 후 currMap 값을 copy
char[][] temp = new char[R][C];
for (int j = 0; j < R; j++) {
System.arraycopy(currMap[j], 0, temp[j], 0, C);
}
int sum = 0; // 감시할 수 있는 영역들의 합
// 방향을 차례로 체크하면서 감시 가능한 모든 영역을 표시
for (int j = 0; j < currCCTV[i].length; j++) {
int d = currCCTV[i][j]; // 체크할 방향
int nr = r + dr[d]; // next r
int nc = c + dc[d]; // next c
// 해당 좌표가 유효하고, 벽이 아니면 계속 반복 수행
while (isValid(nr, nc) && temp[nr][nc] != '6') {
// 만약 CCTV라면 continue
if (temp[nr][nc] != '0' && temp[nr][nc] != '#') {
nr += dr[d];
nc += dc[d];
continue;
}
// 빈 공간이라면 sum - 1
// #은 건너뜀
if (temp[nr][nc] == '0') {
sum++;
}
temp[nr][nc] = '#';
nr += dr[d];
nc += dc[d];
}
}
// 다음 CCTV 재귀호출
watch(no+1, cnt-sum, temp);
}
}
// 좌표의 유효성을 체크하는 메소드
private static boolean isValid(int r, int c) {
if (r<0 || r>=R || c<0 || c>=C) return false;
return true;
}
// cctv의 번호마다 가능한 방향 인덱스를 저장함
private static void cctvInit() {
cctv = new int[6][][];
cctv[1] = new int[][]{ {0}, {1}, {2}, {3} };
cctv[2] = new int[][]{ {0, 1}, {2, 3} };
cctv[3] = new int[][]{ {0, 2}, {0, 3}, {1, 2}, {1, 3} };
cctv[4] = new int[][]{ {0, 1, 2}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3} };
cctv[5] = new int[][]{ {0, 1, 2, 3} };
}
}
마무리
싸피 교육과정을 진행하면서 제가 제일 싫어했던 시뮬레이션(구현력) 유형을 많이 풀어봅니다.
자주, 많이 풀다보니까 여전히 싫긴 하지만 푸는 속도나 정확도가 조금 올라간 것 같아서 괜히 뿌듯하네요 :)
