15683 감시 - 삼성 sw 역량 기출

감시

입력 받을 때 cctv라면 List<int[]>에 추가

​

1.벽이나 맵의 크기보다 밖이 아니라면 방향을 따라 체크할 수 있는 dfs함수 구현

map을 int형으로 만들었기 때문에 -1값으로 바꿔줌

델타 배열을 만들어서 파라미터로 들어오는 방향으로 dfs를 계속하도록 구현

cctv를 통과할 수 있으므로 위 조건을 만족하면 dfs를 계속하지만 현재 좌표가 cctv라면 -1로 변경하지 않고 그대로 두어야함

​

2.모든 cctv의 방향의 경우의 수를 구하는 power함수 구현 : 백트래킹

copymap함수를 구현하여 복사된 copy로 dfs를 하도록 구현 : 원래대로 되돌리지 않고 새로운 맵으로 탐색

리스트에 저장된 cctv의 좌표를 switch문에 넣고 각 cctv마다 볼 수 있는 방향을 돌려가면서 dfs시킴

index가 cctv리스트 사이즈면 맵을 스캔하여 0의 개수를 세고 최소값 변경 후 리턴

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 {
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int[][] map = new int[N][M];
		cctv = new ArrayList<>();
		for(int i = 0; i < N; i++) {
			StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st2.nextToken());
				if(map[i][j]>=1 && map[i][j]<=5) {
					cctv.add(new int[] {i,j});
				}
			}
		}
		ans = Integer.MAX_VALUE;
		power(map, 0);
		System.out.println(ans);


	}

	static List<int[]> cctv;
	static int ans;
	static void power(int[][] map, int idx) {
		if(idx == cctv.size()) {
			int cnt = 0;
			for(int i = 0; i < map.length; i++) {
				for(int j = 0; j < map[i].length; j++) {
					if(map[i][j] == 0)cnt++;
				}
			}
			ans = Math.min(ans, cnt);
			return;
		}
		int y = cctv.get(idx)[0];
		int x = cctv.get(idx)[1];
		int[][] copy = new int[map.length][map[0].length];
		switch(map[y][x]) {
		case 1:
			copymap(map, copy);
			dfs(copy, y, x, 2);
			power(copy, idx+1);

			copymap(map, copy);
			dfs(copy, y, x, 3);
			power(copy, idx+1);

			copymap(map, copy);
			dfs(copy, y, x, 0);
			power(copy, idx+1);

			copymap(map, copy);
			dfs(copy, y, x, 1);
			power(copy, idx+1);
			break;

		case 2:
			copymap(map, copy);
			dfs(copy, y, x, 2);
			dfs(copy, y, x, 3);
			power(copy, idx+1);

			copymap(map, copy);
			dfs(copy, y, x, 0);
			dfs(copy, y, x, 1);
			power(copy, idx+1);
			break;

		case 3:
			copymap(map, copy);
			dfs(copy, y, x, 0);
			dfs(copy, y, x, 3);
			power(copy, idx+1);

			copymap(map,copy);
			dfs(copy, y, x, 3);
			dfs(copy, y, x, 1);
			power(copy, idx+1);

			copymap(map,copy);
			dfs(copy, y, x, 1);
			dfs(copy, y, x, 2);
			power(copy,idx+1);

			copymap(map, copy);
			dfs(copy, y, x, 2);
			dfs(copy, y, x, 0);
			power(copy, idx+1);
			break;

		case 4:
			copymap(map, copy);
			dfs(copy, y, x, 0);
			dfs(copy, y, x, 3);
			dfs(copy, y, x, 2);
			power(copy, idx+1);

			copymap(map,copy);
			dfs(copy, y, x, 3);
			dfs(copy, y, x, 1);
			dfs(copy, y, x, 0);
			power(copy, idx+1);

			copymap(map,copy);
			dfs(copy, y, x, 1);
			dfs(copy, y, x, 2);
			dfs(copy, y, x, 3);
			power(copy,idx+1);

			copymap(map, copy);
			dfs(copy, y, x, 2);
			dfs(copy, y, x, 0);
			dfs(copy, y, x, 1);
			power(copy, idx+1);
			break;

		case 5:
			copymap(map, copy);
			dfs(copy, y, x, 0);
			dfs(copy, y, x, 1);
			dfs(copy, y, x, 2);
			dfs(copy, y, x, 3);
			power(copy, idx+1);
			break;
		}
	}
	static int[] dx = {0,0,-1,1};
	static int[] dy = {-1,1,0,0};

	static void dfs(int[][] map, int y, int x, int dir) {
		int yi = y+dy[dir];
		int xi = x+dx[dir];

		if(yi >= 0 && xi >= 0 && yi < map.length && xi < map[0].length && map[yi][xi]!=6 ){
			if(map[yi][xi]==0) {
				map[yi][xi]=-1;
			}
			dfs(map, yi, xi, dir);
		}


	}
	static void copymap(int[][] map, int[][] copy) {
		for(int i = 0; i < map.length; i++) {
			for(int j = 0; j < map[i].length; j++) {
				copy[i][j] = map[i][j];
			}
		}
	}
}