[골드4] 15683. 감시 (Java)
https://www.acmicpc.net/problem/15683
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
감시하지마
※ 문제를 요약하면 아래와 같습니다.
▶ N x M 크기의 직사각형 맵에 총 K개의 CCTV 설치, CCTV는 아래와 같이 5종류 존재
▶ CCTV는 90도로만 회전이 가능
( 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.)
▶ 맵에 벽이 존재하면 그 이후 방향은 감시 불가
▶ 0은 빈칸, 1~5는 CCTV 번호, 6은 벽으로 주어졌을 때, CCTV가 감시 불가능한 사각 지대의 최소 크기 출력
▶ Input : 첫번째 줄에 공백을 기준으로 세로 크기 N, 가로 크기 M 입력,
이후 N개의 줄에 맵의 상태 입력
▶ Output : 사각 지대 (0) 의 최소 크기 출력
◈ Input - 1
4 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0◈ Output - 1
20◈ Input - 2
6 6
0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 5◈ Output - 2
15◈ Input - 3
8 8
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0◈ Output - 3
64◈ Input - 4
3 7
4 0 0 0 0 0 0
0 0 0 2 0 0 0
0 0 0 0 0 0 4◈ Output - 4
0◎ 코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.
▶ CCTV의 Row,Col 좌표와 번호를 저장할 수 있는 Point 클래스 구현
▶ 맵에 CCTV 좌표를 전부 Point를 제네릭으로 갖는 ArrayList로 저장
▶ CCTV 번호 별 각각 회전이 가능한 경우를 모두 탐색 ==> DFS
1. 0번 부터 ArrayList의 크기까지 각 방향에 대해 전부 감시된 곳을 맵에 7로 표시
2. 각 ArrayList에 임의의 Save 2차원 배열을 만들어 방향 탐색 전 상태 저장
3. CCTV번호에 대한 방향 케이스에 대해 감시한 곳을 7로 표시 후 다음 ArrayList 값으로 재귀
4. 모든 경우를 탐색하여 마지막 cctv에 도달했을 때 0인 곳을 찾아 최소값 비교
▶ 감시 상태 표시는 벽을 만나기 전까지 진행 (다른 CCTV를 마주쳐도 감시 진행 가능)
▶ CCTV가 없을 경우도 존재 (벽을 제외한 모든 곳이 사각 지대)
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Point {
int m_nRow;
int m_nCol;
int m_nNum;
public Point(int m_nRow, int m_nCol, int m_nNum) {
super();
this.m_nRow = m_nRow;
this.m_nCol = m_nCol;
this.m_nNum = m_nNum;
}
}
public class Main {
static int N, M, nMin, nResult;
static int[][] narrMap;
static ArrayList<Point> pCCTV;
// 동, 서, 남, 북
static int[] dr = { 0, 0, 1, -1 };
static int[] dc = { 1, -1, 0, 0 };
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(bReader.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
narrMap = new int[N][M];
pCCTV = new ArrayList<>();
// 맵 값 입력 받고
// CCTV 값들을 저장
for (int i = 0; i < N; i++) {
st = new StringTokenizer(bReader.readLine());
for (int j = 0; j < M; j++) {
narrMap[i][j] = Integer.parseInt(st.nextToken());
if (narrMap[i][j] > 0 && narrMap[i][j] < 6)
pCCTV.add(new Point(i, j, narrMap[i][j]));
}
}
nMin = Integer.MAX_VALUE;
if(!pCCTV.isEmpty()) {
DFS(0);
}
else {
// cctv가 1도 없다.
nMin = getZeroCount();
}
if(nMin == Integer.MAX_VALUE)
nMin = 0;
bWriter.write(String.valueOf(nMin));
bWriter.close();
}
// N과 M 형태로 풀어볼까,,,?
private static void DFS(int nCount) {
// 탐색 종료 조건
if (nCount == pCCTV.size()) {
// 제로가 몇개인지 세구
// 비교하자
int nZero = getZeroCount();
if (nMin > nZero) {
nMin = nZero;
}
return;
}
Point pPoint = pCCTV.get(nCount);
int[][] narrSave = new int[N][M];
// 탐색 전 상태의 Map을 저장해놓구
// 탐색 후에 해당 탐색의 직전 상태로 돌려놓자
copy(narrSave, narrMap);
// 1번, 동,서,남,북 네 방향
if (pPoint.m_nNum == 1) {
for (int i = 0; i < dr.length; i++) {
checkCCTV(pPoint.m_nRow, pPoint.m_nCol, i);
DFS(nCount + 1);
copy(narrMap, narrSave);
}
} else if (pPoint.m_nNum == 2) {
// 2번, 동서, 남북 두방향
for (int i = 0; i < dr.length; i += 2) {
checkCCTV(pPoint.m_nRow, pPoint.m_nCol, i);
checkCCTV(pPoint.m_nRow, pPoint.m_nCol, i + 1);
DFS(nCount + 1);
copy(narrMap, narrSave);
}
} else if (pPoint.m_nNum == 3) {
// 3번, 북동, 동남, 남서, 서북 4방향
for (int i = 2; i < dr.length; i++) {
for (int j = 0; j < 2; j++) {
checkCCTV(pPoint.m_nRow, pPoint.m_nCol, i);
checkCCTV(pPoint.m_nRow, pPoint.m_nCol, j);
DFS(nCount + 1);
copy(narrMap, narrSave);
}
}
} else if (pPoint.m_nNum == 4) {
// 4번, 4방향 전부 탐색에서 하나씩 뺀거
for (int i = 0; i < dr.length; i++) {
for(int j = i; j < i+3; j++) {
int nDirect = j;
if(nDirect > 3)
nDirect -= 4;
checkCCTV(pPoint.m_nRow, pPoint.m_nCol, nDirect);
}
DFS(nCount + 1);
copy(narrMap, narrSave);
}
} else if (pPoint.m_nNum == 5) {
// 모든 방향
for (int i = 0; i < dr.length; i++) {
checkCCTV(pPoint.m_nRow, pPoint.m_nCol, i);
}
DFS(nCount + 1);
copy(narrMap, narrSave);
}
}
// 사각지대 갯수 뽑자
private static int getZeroCount() {
int nCount = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (narrMap[i][j] == 0)
nCount++;
}
}
return nCount;
}
// CCTV가 보는 방향을 체크해두자
private static void checkCCTV(int nRow, int nCol, int nDirect) {
int nSearchRow = nRow + dr[nDirect];
int nSearchCol = nCol + dc[nDirect];
while (nSearchRow >= 0 && nSearchCol >= 0 && nSearchRow < N && nSearchCol < M) {
if (narrMap[nSearchRow][nSearchCol] == 0)
narrMap[nSearchRow][nSearchCol] = 7;
else if (narrMap[nSearchRow][nSearchCol] == 6) // 오직 벽만 break
break;
nSearchRow += dr[nDirect];
nSearchCol += dc[nDirect];
}
}
private static void copy(int[][] narrTo, int[][] narrFrom) {
// 임시 템플릿 배열에 복사해놓자
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
narrTo[i][j] = narrFrom[i][j];
}
}
}
}Good Luck! (피드백 감사합니다!)