[BOJ-15683] 감시 -Java

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

15683번: 감시

package 시뮬레이션;

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 boj_15683_감시 {
	static class Cctv {
		int x, y, no;
		public Cctv(int x, int y, int no) {
			this.x = x;
			this.y = y;
			this.no = no;
		}
	}
	static List<Cctv> cctvList = new ArrayList<>();
	static int N, M, result;
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	static int dir[][] = { 
			{}, 
			{ 0 }, 
			{ 0, 2 }, 
			{ 0, 1 }, 
			{ 0, 1, 2 }, 
			{ 0, 1, 2, 3 }, 
			};

	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());
		int[][] map = new int[N][M];
		result=Integer.MAX_VALUE;

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] != 0 && map[i][j] != 6)
					cctvList.add(new Cctv(i, j, map[i][j]));
			}
		}
		solve(0, cctvList.size(), map);
		System.out.println(result);
	}

	private static void solve(int cnt, int size, int[][] map) {
		if (cnt == size) {
			int zeroCnt=0;
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) {
					if(map[i][j]==0) zeroCnt++; 
				}
			}
			result = Math.min(result, zeroCnt);
			return;
		}
		for (int d = 0; d < 4; d++) {

			int[][] copy = new int[N][M];
			for (int i = 0; i < map.length; i++) {
				System.arraycopy(map[i], 0, copy[i], 0, M);
			}

			Cctv cctv = cctvList.get(cnt);

			for (int i = 0; i < dir[cctv.no].length; i++) {
				int nx=cctv.x;
				int ny=cctv.y;
				while(true) {
					nx += dx[(dir[cctv.no][i]+d)%4];
				    ny += dy[(dir[cctv.no][i]+d)%4];
				    
				    if(nx<0 || ny<0 || nx>=N || ny>=M || copy[nx][ny]==6) break;
				    if(copy[nx][ny]!=0) continue;
				    copy[nx][ny]=7;
				}
			}
			solve(cnt + 1, size,copy);
		}
	}

}

소요시간:45분

 

2차원 dir배열을 통해 각 cctv가 볼 수 있는 경우의 수 중 1개의 경우의 수만 저장하였습니다.

예를 들어 1번 cctv는 0, 1, 2, 3 을 다 한번씩 봐야 하기 때문에 dir배열에는 0만 넣어두고 for문을 돌려서 d를 0~3으로 만들어 각각의 방향에 더해주었습니다.  1번 cctv는 0+0, 0+1, 0+2, 0+3 식으로 진행이 되게 만들었습니다.

 

cctvList에는 각 cctv의 좌표와 번호를 저장해서 사용했습니다.

 

DFS를 사용했고 cctv가 확인할 수 있는 구역은 7로 배열을 채웠습니다.

 

DFS에서 다음 DFS로 넘어가면 파라미터로 받은 map을 copy라는 배열에 복사해줍니다!

복사를 해주는 이유는 만약 맵상의 cctv가 여러개 있다면 한개의 cctv방향을 설정해서 copy맵에 7로 그려주고 그 상태를 유지하면서 앞으로 쭉 갔다가 뒤로 돌아올 땐 다시 map을 되돌려줘야 하기 때문입니다!