[BOJ 15683] 감시 (Java)

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

15683번: 감시

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

public class Main_BOJ_15683 {
	static int N, M;
	static int[][] map;
	static int[][] temp;
	static int[] dy= {-1,0,1,0};
	static int[] dx= {0,1,0,-1};
	static int[] dir= {-1,4,2,4,4,1};
	static int answer=Integer.MAX_VALUE;
	static List<Cam> li=new ArrayList<>();
	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());
		map=new int[N][M];
		temp=new int[N][M];
		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());
				temp[i][j]=map[i][j];
				if (map[i][j]!=0 && map[i][j]!=6) {
					li.add(new Cam(map[i][j], i, j));
				}
			}
		}
		if (li.size()>0) {
			getDir(0);	
		}
		else {
			check();
		}
		System.out.println(answer);

	}
	
	
	private static void getDir(int idx) {		//각 direction 정해줌
		if (idx==li.size()) {
			for (int i=0; i<li.size(); i++) {
				Cam c=li.get(i);
				search(c.r, c.c, generateDir(c.num, c.d));
			}
			check();
			for (int i=0; i<N; i++) {
				map[i]=Arrays.copyOf(temp[i], M);
			}
			return;
		}
		Cam c=li.get(idx);
		for (int i=0; i<dir[c.num]; i++) {
			c.d=i;
			getDir(idx+1);
		}
		
	}

	private static void check() {
		int cnt=0;
		for (int i=0; i<N; i++) {
			for (int j=0; j<M; j++) {
				if (map[i][j]==0) {
					cnt++;
				}
			}
		}
		answer=Math.min(answer, cnt);
	}


	private static void search(int r, int c, int[] dd) {
		int start_r=r;
		int start_c=c;
		for (int i=0; i<dd.length; i++) {
			r=start_r;
			c=start_c;
			while (true) {
				int nr=r+dy[dd[i]];
				int nc=c+dx[dd[i]];
				if (nr<0 || nc<0 || nr>=N || nc>=M || map[nr][nc]==6) break;
				if (map[nr][nc]==0) {
					map[nr][nc]=7;
				}
				r=nr;
				c=nc;
			}
		}
		
	}

	private static int[] generateDir(int num, int d) {
		int[] dd=new int[1];
		switch(num) {
		case 1:
			dd=new int[1];
			dd[0]=d;
			break;
		case 2:
			dd=new int[2];
			dd[0]=d;
			dd[1]=(d+2)%4;
			break;
		case 3:
			dd=new int[2];
			dd[0]=d;
			dd[1]=(d+1)%4;
			break;
		case 4:
			dd=new int[3];
			dd[0]=d;
			dd[1]=(d+1)%4;
			dd[2]=(d-1+4)%4;
			break;
		case 5:
			dd=new int[4];
			dd[0]=0; dd[1]=1; dd[2]=2; dd[3]=3;
			break;
		}
		return dd;
	}

	public static class Cam{
		int num;
		int r,c,d;
		private Cam(int num, int r, int c) {
			this.num = num;
			this.r = r;
			this.c = c;
		}
		
	}

}

각 감시 카메라의 위치, 번호를 저장해 arraylist에 넣는다.

이때, 각 감시 카메라마다 나올 수 있는 경우의 수만큼 그 모든 경우를 고려해준다. 

getDir 함수는 각 감시 카메라의 direction 시작점을 정하고, 모두 시작점을 정했으면 각 감시 카메라마다 탐색할 direction 을 만들어준다. (generateDir 함수로, direction 시작점을 구하면 각 감시 카메라의 번호마다 탐색할 방향을 배열에 넣어서 반환한다.)

탐색할 direction이 만들어졌으면, search 함수로 각 방향들을 모두 탐색해준다.

이때 탐색할 때, 0이 있는 경우는 7로 방문표시를 해주고, 벽을 만났거나 영역을 벗어났을땐 탐색을 종료한다.

다른 방향을 탐색할 때는 반드시 시작점을 처음 r,c 로 돌려줘야 한다. (이거때문에 삽질했다).

모든 카메라에 대해 이 연산이 끝나면 check 함수를 이용해 사각지대 영역을 세어 주고, 다시 map을 처음 상태로 원상 복귀해 다음 탐색을 할 준비를 한다..

 

이 문제의 포인트는 dfs 로 완전 탐색을 하는 것이다.

 

그런데 조금 복잡하게 풀었다.

이렇게 다 분리해 줄 필요 없이, 각 카메라의 탐색 방향 시작점을 선정하고, 그 방향까지 다 탐색해 준 후 계속해서 dfs 를 돌리는 방식을 취하면 구조가 간단해진다. 

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

public class Main_BOJ_15683_2 {
	static int N, M;
	static int[][] map;
	static int[] dy= {-1,0,1,0};
	static int[] dx= {0,1,0,-1};
	static int answer=Integer.MAX_VALUE;
	static List<Cam> li=new ArrayList<>();
	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());
		map=new int[N][M];
		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) {
					li.add(new Cam(map[i][j], i, j));
				}
			}
		}
		if (li.size()>0) {
			dfs(0, map);
		}
		else {
			check(map);
		}
		System.out.println(answer);

	}
	

	private static void dfs(int cnt, int[][] map) {
		if (cnt==li.size()) {
			check(map);
			return;
		}
		Cam cam=li.get(cnt);
		if (cam.num==1) {
			for (int d=0; d<4; d++) {
				int[][] vMap=copyMap(map);
				visit(cam.r, cam.c, d, vMap);
				dfs(cnt+1, vMap);
			}
		}
		else if (cam.num==2) {
			for (int d=0; d<2; d++) {
				int[][] vMap=copyMap(map);
				visit(cam.r, cam.c, d, vMap);
				visit(cam.r, cam.c, (d+2)%4, vMap);
				dfs(cnt+1, vMap);
			}
		}
		else if (cam.num==3) {
			for (int d=0; d<4; d++) {
				int[][] vMap=copyMap(map);
				visit(cam.r, cam.c, d, vMap);
				visit(cam.r, cam.c, (d+1)%4, vMap);
				dfs(cnt+1, vMap);
			}
		}
		else if (cam.num==4) {
			for (int d=0; d<4; d++) {
				int[][] vMap=copyMap(map);
				visit(cam.r, cam.c, d, vMap);
				visit(cam.r, cam.c, (d+1)%4, vMap);
				visit(cam.r, cam.c, (d-1+4)%4, vMap);
				dfs(cnt+1, vMap);
			}
		}
		else if (cam.num==5) {
			for (int d=0; d<1; d++) {
				int[][] vMap=copyMap(map);
				visit(cam.r, cam.c, d, vMap);
				visit(cam.r, cam.c, (d+1)%4, vMap);
				visit(cam.r, cam.c, (d+2)%4, vMap);
				visit(cam.r, cam.c, (d+3)%4, vMap);
				dfs(cnt+1, vMap);
			}
		}
		
		
	}
	
	private static void visit(int r, int c, int d, int[][] vMap) {
		while (true) {
			int nr=r+dy[d];
			int nc=c+dx[d];
			if (nr<0 || nc<0 || nr>=N || nc>=M || vMap[nr][nc]==6) break;
			if (vMap[nr][nc]==0) {
				vMap[nr][nc]=7;
			}
			r=nr;
			c=nc;
		}
	}


	private static int[][] copyMap(int[][] map){
		int[][] vMap=new int[N][M];
		for (int i=0; i<N; i++) {
			vMap[i]=Arrays.copyOf(map[i], M);
		}
		return vMap;
	}


	private static void check(int[][] m) {
		int cnt=0;
		for (int i=0; i<N; i++) {
			for (int j=0; j<M; j++) {
				if (m[i][j]==0) {
					cnt++;
				}
			}
		}
		answer=Math.min(answer, cnt);
	}

	public static class Cam{
		int num;
		int r,c;
		private Cam(int num, int r, int c) {
			this.num = num;
			this.r = r;
			this.c = c;
		}
		
	}

}

바로 위에 코드는 다른 방식으로 한번 더 짜본 코드다.

해당 카메라 넘버에 방향을 정하고, map에다 표시해주고, 또 dfs 해서 이동하고. .해서 N 개의 카메라에 모두 도달할 때 체크해준다. DFS 로 모든 경우의 수가 체크된다.