문제

BOJ 15683: 감시 https://www.acmicpc.net/problem/15683

풀이

• ArrayList에 캠의 종류와 좌표를 넣는다.

  • caseList 에 캠의 종류와 감시 방향에 대한 정보를 넣는다.

    caseList에 들어가는 배열의 0번째 자리에는 캠의 종류에 대한 정보가 들어간다.
    예를 들어,

    • 1번 캠: caseList.add(new int[] {1, 1, 2, 3, 4}); ----> 1번 캠, 방향 1 2 3 4
    • 2번 캠: caseList.add(new int[] {2, 1, 2}); ----> 2번 캠, 방향 1 2

• 백트래킹을 사용하여 각 캠의 감시 방향을 조합한다.

  • 백트래킹의 종료 조건에서 배열의 깊은 복사를 사용하는 이유는 캠이 감시한 방향에 표시를 해줄건데 이 표시의 중복처리를 방지하기 위함이다.

• 캠 종류에 따른 처리와 캠 감시 방향에 따른 처리는 별도의 메소드를 만들어 사용한다.

• 배열의 깊은 복사 는 이 블로그 Java 배열의 얕은 복사 & 깊은 복사에서 확인할 수 있다.

코드

import java.util.*;
import java.io.*;

public class Main {
	
	static int N, M; 
	static int[][] newMap; // 복사해서 쓸 배열
	static int[][] baseMap; // 원본 배열
	static int camCnt = 0; // 카메라 개수
	static int[][] newCamArr; // 캠 방향 조합할 배열
	static ArrayList<int[]> caseList = new ArrayList<>(); // 캠 종류, 방향
	static ArrayList<Pos> camXY = new ArrayList<>(); // 캠 좌표
	static int min = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken()); // 세로 크기
		M = Integer.parseInt(st.nextToken()); // 가로 크기
	
		baseMap = new int[N][M];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<M; j++) {
				baseMap[i][j] = Integer.parseInt(st.nextToken());
				if(baseMap[i][j] != 0 && baseMap[i][j] != 6) {
					camCnt++;
					if(baseMap[i][j] == 1) {
						caseList.add(new int[] {1, 1, 2, 3, 4}); // 1번 캠, 방향 1 2 3 4
						camXY.add(new Pos(i, j));
					}
					else if(baseMap[i][j] == 2) {
						caseList.add(new int[] {2, 1, 2}); // 2번 캠, 방향 1 2
						camXY.add(new Pos(i, j));
					}
					else if(baseMap[i][j] == 3) {
						caseList.add(new int[] {3, 1, 2, 3, 4}); // 3번 캠, 방향 1 2 3 4
						camXY.add(new Pos(i, j));
					}
					else if(baseMap[i][j] == 4) {
						caseList.add(new int[] {4, 1, 2, 3, 4}); // 4번 캠, 방향 1 2 3 4
						camXY.add(new Pos(i, j));
					}
					else if(baseMap[i][j] == 5) {
						caseList.add(new int[] {5, 1}); // 5번 캠, 방향 1
						camXY.add(new Pos(i, j));
					}
				}
			}
		}
		
		newCamArr = new int[2][caseList.size()];
		
		camBT(0);
		
		System.out.println(min);
	}
	//카메라 방향별로 조합
	static void camBT(int depth) {
		if(depth == caseList.size()) {
			// 새로운 배열 깊은 복사
			newMap = new int[baseMap.length][baseMap[0].length];
			for(int i=0; i<baseMap.length; i++) {
				for(int j=0; j<baseMap[0].length; j++) {
					newMap[i][j] = baseMap[i][j];
				}
			}
			// 조합을 넣은 배열 내 값을 차례로 보면서 watch() 수행
			for(int i=0; i<caseList.size(); i++) {
				int camNum = newCamArr[0][i]; // 캠 종류
				int camDir = newCamArr[1][i]; // 캠 방향
				
				watch(i, camNum, camDir);	
				
			}
			// 사각지대의 크기를 구함
			int cnt = 0;
			for(int r=0; r<N; r++) {
				for(int c=0; c<M; c++) {
					if(newMap[r][c] == 0) {
						cnt++;
					}
				}
			}
			// 사각지대 최솟값 구함
			min = Math.min(min, cnt);
			return;
		}
		
		//캠 방향을 조합함 -> depth 자체가 리스트에 들어온 캠 순서를 나타내기 때문
		for(int j=1; j<caseList.get(depth).length; j++) {
			newCamArr[0][depth] = caseList.get(depth)[0]; // 캠 종류
			newCamArr[1][depth] = caseList.get(depth)[j]; // 캠 방향
			camBT(depth + 1);
		}
		
	}
	// 캠으로 볼 수 있는 방향을 캠 종류와 방향에 따라 수행함
	static void watch(int newCamArrIdx, int camNum, int dir) {
		/*
		 * newCamArrIdx: 리스트에 있는 캠을 리스트의 인덱스로 찾음
		 * camNum: 캠 종류
		 * dir: 조합으로 나온 방향
		 */
		Pos p = camXY.get(newCamArrIdx);
		int x = p.x;
		int y = p.y;
		
		switch(camNum) {
			case 1: cam1(dir, x, y);
				break;
			case 2: cam2(dir, x, y);
				break;
			case 3: cam3(dir, x, y);
				break;
			case 4: cam4(dir, x, y);
				break;
			case 5: cam5(dir, x, y);
				break;
			default: System.out.println("watch error");
				break;
		}
	}
	// 캠 왼쪽을 감시
	static void watchLeft(int x, int y) {
		for(int i=y; i>=0; i--) {
			if(newMap[x][i] == 6) {
				break;
			}
			// 다른 카메라면 통과
			if(newMap[x][i] != 0) {
				continue;
			}
			newMap[x][i] = 9;
		}
	}
	// 캠 윗쪽을 감시
	static void watchTop(int x, int y) {
		for(int i=x; i>=0; i--) {
			if(newMap[i][y] == 6) {
				break;
			}
			// 다른 카메라면 통과
			if(newMap[i][y] != 0) {
				continue;
			}
			newMap[i][y] = 9;
		}
	}
	// 캠 오른쪽을 감시
	static void watchRight(int x, int y) {
		for(int i=y; i<=M-1; i++) {
			if(newMap[x][i] == 6) {
				break;
			}
			// 다른 카메라면 통과
			if(newMap[x][i] != 0) {
				continue;
			}
			newMap[x][i] = 9;
		}
	}
	// 캠 아랫쪽을 감시
	static void watchBottom(int x, int y) {
		for(int i=x; i<=N-1; i++) {
			if(newMap[i][y] == 6) {
				break;
			}
			// 다른 카메라면 통과
			if(newMap[i][y] != 0) {
				continue;
			}
			newMap[i][y] = 9;
		}
	}
	// 1번 캠의 방향
	static void cam1(int direction, int x, int y) {
		// 카메라가 보는 방향은 9를 넣음
		switch(direction) {
		case 1: 
			watchLeft(x, y);
			break;
		case 2:
			watchTop(x, y);
			break;
		case 3:
			watchRight(x, y);
			break;
		case 4:
			watchBottom(x, y);
			break;
		default: System.out.println("cam1 error");
			break;
		}
	}
	// 2번 캠의 방향
	static void cam2(int direction, int x, int y) {
		// 카메라가 보는 방향은 9를 넣음
		switch(direction) {
		case 1: 
			watchLeft(x, y);
			watchRight(x, y);
			break;
		case 2:
			watchTop(x, y);
			watchBottom(x, y);
			break;
		default: System.out.println("cam2 error");
			break;
		}
	}
	// 3번 캠의 방향
	static void cam3(int direction, int x, int y) {
		// 카메라가 보는 방향은 9를 넣음
		switch(direction) {
		case 1: 
			watchLeft(x, y);
			watchTop(x, y);
			break;
		case 2:
			watchTop(x, y);
			watchRight(x, y);
			break;
		case 3:
			watchRight(x, y);
			watchBottom(x, y);
			break;
		case 4:
			watchBottom(x, y);
			watchLeft(x, y);
			break;
		default: System.out.println("cam3 error");
			break;
		}
	}
	// 4번 캠의 방향
	static void cam4(int direction, int x, int y) {
		// 카메라가 보는 방향은 9를 넣음
		switch(direction) {
		case 1: 
			watchLeft(x, y);
			watchTop(x, y);
			watchRight(x, y);
			break;
		case 2:
			watchTop(x, y);
			watchRight(x, y);
			watchBottom(x, y);
			break;
		case 3:
			watchLeft(x, y);
			watchBottom(x, y);
			watchRight(x, y);
			break;
		case 4:
			watchTop(x, y);
			watchLeft(x, y);
			watchBottom(x, y);
			break;
		default: System.out.println("cam4 error");
			break;
		}
	}
	// 5번 캠의 방향
	static void cam5(int direction, int x, int y) {
		// 카메라가 보는 방향은 9를 넣음
		switch(direction) {
		case 1: 
			watchLeft(x, y);
			watchTop(x, y);
			watchRight(x, y);
			watchBottom(x, y);
			break;
		default: System.out.println("cam5 error");
			break;
		}
	}
	
	static class Pos{

		int x, y;
		
		Pos(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
}

정리

• 배열의 깊은 복사를 사용하지 않아 감시 방향이 중복 처리 되어 오류가 나왔었다.
• 백트래킹 내에서 재귀호출을 해줄 때

		//캠 방향을 조합함 -> depth 자체가 리스트에 들어온 캠 순서를 나타내기 때문
		for(int j=1; j<caseList.get(depth).length; j++) {
               newCamArr[0][depth] = caseList.get(depth)[0]; // 캠 종류
               newCamArr[1][depth] = caseList.get(depth)[j]; // 캠 방향
               camBT(depth + 1);
		}

대신

		for(int i=0; i<caseList.size(); i++) {
			for(int j=1; j<caseList.get(i).length; j++) {
				newCamArr[0][depth] = caseList.get(i)[0]; // 캠 종류
				newCamArr[1][depth] = caseList.get(i)[j]; // 캠 방향
				camBT(depth + 1);
			}
		}

을 해서 틀렸었다.