백준 15683번: 감시

문제 설명

• https://www.acmicpc.net/problem/15683

접근법

• 백트래킹을 활용한 구현 문제입니다.
  • 카메라별로 가능한 방향의 경우의 수를 모두 고려해 줘야 합니다.
  • 백트래킹 함수에서 forEach문을 사용한 부분이 그러한 내용에 해당합니다.

for (i = start; i<size; i++){
	for(Dist d: Candi(num)){
    	BackT
    }	
}

• 2차원 배열에 값을 변경한 뒤 BackT에 넣고, 다음 값을 위해 원래대로 되돌리는 방법
  • 저는 list에 값을 변경한 위치를 담아두었습니다.
  • board를 copy해 지속적으로 사용하는 방법도 있습니다.

정답

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

public class Main {
	static int N,M;
	static int[] dx = {0,0,-1,1}; // 왼,오,위,아래
	static int[] dy = {-1,1,0,0};
	static int minVal = Integer.MAX_VALUE;
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		int[][] board = new int[N][M];
		List<int[]> camera = new ArrayList<int[]>();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				board[i][j] = sc.nextInt();
				if(0< board[i][j] && board[i][j] <6) {
					camera.add(new int[] {i,j});
				}
			}
		}

		int size = camera.size();	


		BackT(board, 0, size,new boolean[size],0,new int[size],camera);
		System.out.println(minVal);
	}

	public static void BackT(int[][] board, int depth, int size,boolean[] v , int start, int[] answer,List<int[]> camera) {
		if(depth == size) {
			minVal = Math.min(minVal, Score(board));
			return;
		}
		for (int i = start; i < size; i++) {
			if(v[i]) continue;
			int[] cam = camera.get(i);
			int num = board[cam[0]][cam[1]];
			for (Dist d : Candi(num)) { // 해당 카메라의 방향을 고려
				v[i] = true;
				List<int[]> pos = Scan(d,cam,9,board); // 해당 방향으로 감시했다는 표시(9)를 하고, 어디에 표시해뒀는지를 pos라는 리스트에 담음
				BackT(board,depth+1,size,v,i,answer,camera);
				// 해당 방향으로 감시했다는 표시(9)를 지움
				for (int j = 0; j < pos.size(); j++) {
					int[] now = pos.get(j);
					board[now[0]][now[1]] = 0;
				}
				v[i] = false;
			}
			
		}
	}
	
	// 주어진 방향으로 감시를 진행
	public static List<int[]> Scan(Dist d, int[] cam, int val,int[][] board) {
		List<int[]> pos = new ArrayList<int[]>();
		if(d.left) {
			int x = cam[0];
			int y = cam[1];
			while(true) {
				x = x+dx[0];
				y = y+dy[0];
				if(0 > x || x >= N || 0 > y || y > M) break;
				if(board[x][y] == 0) {
					board[x][y] = val;
					pos.add(new int[] {x,y});
				}else if(board[x][y] == 6) {
					break;
				}else {
					continue;
				}
				
			}
		}
		if(d.right) {
			int x = cam[0];
			int y = cam[1];
			while(true) {
				x = x+dx[1];
				y = y+dy[1];
				if(0 > x || x >= N || 0 > y || y >= M) break;
				if(board[x][y] == 0) {
					board[x][y] = val;					
					pos.add(new int[] {x,y});
				}else if(board[x][y] == 6) {
					break;
				}else {

					continue;
				}
				
			}
		}
		if(d.up) {
			int x = cam[0];
			int y = cam[1];
			while(true) {
				x = x+dx[2];
				y = y+dy[2];
				if(0 > x || x >= N || 0 > y || y > M) break;
				if(board[x][y] == 0) {
					board[x][y] = val;					
					pos.add(new int[] {x,y});
				}else if(board[x][y] == 6) {
					break;
				}else {

					continue;
				}
				
			}
		}
		if(d.down) {
			int x = cam[0];
			int y = cam[1];
			while(true) {
				x = x+dx[3];
				y = y+dy[3];
				if(0 > x || x >= N || 0 > y || y > M) break;
				if(board[x][y] == 0) {
					board[x][y] = val;					
					pos.add(new int[] {x,y});
				}else if(board[x][y] == 6) {
					break;
				}else {

					continue;
				}
				
			}
		}
		return pos;
	}
	
	// 카메라 종류에 따라 가능한 경우의 수
	public static List<Dist> Candi(int num) {
		List<Dist> candi = new ArrayList<Dist>();
		if(num == 1) {
			candi.add(new Dist(true,false,false,false));
			candi.add(new Dist(false,true,false,false));
			candi.add(new Dist(false,false,true,false));
			candi.add(new Dist(false,false,false,true));
		}else if(num == 2) {
			candi.add(new Dist(true,true,false,false));
			candi.add(new Dist(false,false,true,true));			
		}else if(num == 3) {
			candi.add(new Dist(true,false,true,false));
			candi.add(new Dist(true,false,false,true));
			candi.add(new Dist(false,true,false,true));
			candi.add(new Dist(false,true,true,false));			
		}else if(num == 4) {
			candi.add(new Dist(true,true,true,false));
			candi.add(new Dist(true,true,false,true));
			candi.add(new Dist(true,false,true,true));
			candi.add(new Dist(false,true,true,true));
		}else if(num ==5) {
			candi.add(new Dist(true,true,true,true));
		}
		return candi;
	}
	
	
	// 최종적으로 몇 군데가 감시 불가능한지 반환
	public static int Score(int[][] board) {
		int score = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(board[i][j] == 0) score++;
			}
		}
		return score;
	}
	
	// 카메라가 어딜 보고 있는지
	static class Dist{
		boolean left;
		boolean right;
		boolean up;
		boolean down;
		public Dist(boolean left, boolean right, boolean up, boolean down) {
			super();
			this.left = left;
			this.right = right;
			this.up = up;
			this.down = down;
		}
		@Override
		public String toString() {
			return "Dist [left=" + left + ", right=" + right + ", up=" + up + ", down=" + down + "]";
		}
		
		
		
	}
}