[백준] 15683. 감시 (Java)

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

15683번: 감시

 

💡 브루트포스 → dfs

 

✔️ 한 번에 통과 못 한 이유

• cctv 4번의 감시 구역 방향 설정을 제대로 못했다. 4번의 {0,1,3},{0,1,2} 이 두개를 빼먹고 풀어서 틀렸다.

static int[][][] move = {
			{{0}},
			{{0},{1},{2},{3}},// 1번
			{{0,1},{2,3}}, // 2번
			{{0,3},{1,3},{1,2},{2,0}}, // 3번
			{{0,2,3},{1,2,3},{0,1,3},{0,1,2}}, // 4번
			{{0,1,2,3}}, // 5번
	};

• cctv는 cctv를 통과할 수 있다 → 이 조건을 잊고 있었다.
• 재귀함수에서 돌아오고 난 뒤, 기존 배열 값으로 초기화 해줘야 한다. → 이 조건을 처리 안 해줬다.

 

문제에서 주어진 조건을 빼먹지 말고 차분하게 풀자.

 

✔️ 문제 풀이

1. 입력을 받으면서 ArrayList에 CCTV의 좌표값과 감시 카메라의 유형을 저장한다.
2. 재귀함수로 감시 카메라 유형 별 가능한 방향을 모두 확인한다.
3. 감시카메라 개수만큼 모두 확인할 때 마다 result에 최소값을 넣어준다.

 

✅ 정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	
	static int N,M,result;
	static int[][] board;
	static int[][][] move = {
			{{0}},
			{{0},{1},{2},{3}},
			{{0,1},{2,3}},
			{{0,3},{1,3},{1,2},{2,0}},
			{{0,2,3},{1,2,3},{0,1,3},{0,1,2}},
			{{0,1,2,3}},
	};
	static ArrayList<Point> cctvList;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	static class Point {
		int type,x,y;
		public Point(int type, int x, int y) {
			this.type = type;
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		board = new int[N][M];
		cctvList = new ArrayList<>();
		int cnt = N * M; // 처음 0 개수
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<M;j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
				if(board[i][j] >= 1 && board[i][j] <= 5) {
					cctvList.add(new Point(board[i][j],i,j));
					cnt--;
				}
				if(board[i][j] == 6) cnt--;
			}
		} // input end
		
		result = Integer.MAX_VALUE;
		
		solve(0,cnt,board);
		
		System.out.println(result);
	}

	private static void solve(int idx, int cnt, int[][] arr) {
		if(idx == cctvList.size()) {
			result = Math.min(result, cnt);
			return;
		}
		
		Point temp = cctvList.get(idx);
		int x = temp.x;
		int y = temp.y;
		
		int[][] arr_copy = new int[N][M];
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				arr_copy[i][j] = arr[i][j];
			}
		}
		
		for(int i=0;i<move[temp.type].length;i++) {
			int count = cnt;
			for(int j=0;j<move[temp.type][i].length;j++) {
				int d = move[temp.type][i][j];
				int nx = x + dx[d];
				int ny = y + dy[d];
				
				while(isValid(nx,ny)) {
					if(arr_copy[nx][ny] == 0) {
						count--;
						arr_copy[nx][ny] = -1;
					}
					if(arr_copy[nx][ny] == 6) break;
					
					nx += dx[d];
					ny += dy[d];
				}
				
			}
			
			solve(idx+1, count, arr_copy);
			// 재귀에서 돌아온 후, 이전 배열 값으로 초기화
			for(int k=0;k<N;k++) {
				for(int j=0;j<M;j++) {
					arr_copy[k][j] = arr[k][j];
				}
			}
		}
	}
	
	private static boolean isValid(int r, int c) {
		if(r<0 || c<0 || r>=N || c>=M) return false;
		return true;
	}

}