[백준15683] 감시 - 자바(JAVA)

1. 문제

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

15683번: 감시

 

2. 풀이+소감(?)

핵심만 설명하겠다.

먼저 cctv 정보(타입, 좌표)를 저장할 클래스를 만들어 줬다.

그다음 반복문을 돌면서 cctv정보를 ArrayList에 저장해줬다.

cctv정보를 편리하게 조회할 수 있도록 해야겠다는 생각이 들어서 클래스를 만들고 ArrayList에 저장하는게 핵심

 

그리고 dfs를 수행하면서 감시 구역을 찾아갔다.

cctv 방향을 바꿔가면서 탐색해야하는데 나는 규칙은 찾기 어려워서 cctv마다 일일이 방향을 바꿔주었다. 덕분에 코드가 엄청 길어짐ㅎㅎ

또 새로 탐색할 때마다 배열을 공유하면 안되니까 배열을 복사해줘야했는데 처음엔 map.clone()을 하다가 디버깅 도중에 이상함을 발견하고 검색해봤더니 map.clone()을하면 객체를 담은 주소값을 복사해 새로 생성하기 때문에 1차원 배열이랑 다르게 clone()을 쓰면 안되고 반복문으로 일일이 복사해야된다는 걸 배웠다.

 

 

3. 코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	
	static int N,M;
	static List<CCTV> cctv;
	static int min=Integer.MAX_VALUE;
	
	static class CCTV {
		int type; //1~5
		int x; //M
		int y; //N
		
		public CCTV(int type, int x, int y) {
			this.type=type;
			this.x=x;
			this.y=y;
		}
	}
	
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		
		N=sc.nextInt();
		M=sc.nextInt();
		
		int[][] map=new int[N][M];
		cctv=new ArrayList<CCTV>();
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				map[i][j]=sc.nextInt();
				if(map[i][j]!=0&&map[i][j]!=6)
					cctv.add(new CCTV(map[i][j],j,i));
			}
		}
		
		dfs(0,map);
		
		System.out.println(min);
	}
	
	public static void dfs(int depth,int[][] map) {
		if(depth==cctv.size()) {
			int cnt=0;
//			System.out.println("시작");
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
//					System.out.print(map[i][j]+" ");
					if(map[i][j]==0) cnt++;
				}
//				System.out.println();
			}
			min=Math.min(cnt, min);
			return;
		}
	
		
		CCTV obj=cctv.get(depth);
		int[][] tmp;
		
		switch(obj.type) {
		case 1:
			tmp=copyMap(map);
			checkRight(tmp,obj.x,obj.y);
			dfs(depth+1,tmp);
			
			tmp=copyMap(map);
			checkDown(tmp,obj.x,obj.y);
			dfs(depth+1,tmp);
			
			tmp=copyMap(map);
			checkLeft(tmp,obj.x,obj.y);
			dfs(depth+1,tmp);
			
			tmp=copyMap(map);
			checkUp(tmp,obj.x,obj.y);
			dfs(depth+1,tmp);
			break;
		case 2:
			tmp=copyMap(map);
			checkRight(tmp,obj.x,obj.y);
			checkLeft(tmp,obj.x,obj.y);
			dfs(depth+1,tmp);
			
			tmp=copyMap(map);
			checkUp(tmp,obj.x,obj.y);
			checkDown(tmp,obj.x,obj.y);
			dfs(depth+1,tmp);
			break;
		case 3:
			tmp=copyMap(map);
			checkUp(tmp,obj.x,obj.y);
			checkRight(tmp,obj.x,obj.y);
			dfs(depth+1,tmp);
			
			tmp=copyMap(map);
			checkRight(tmp,obj.x,obj.y);
			checkDown(tmp,obj.x,obj.y);
			dfs(depth+1,tmp);
			
			tmp=copyMap(map);
			checkDown(tmp,obj.x,obj.y);
			checkLeft(tmp,obj.x,obj.y);
			dfs(depth+1,tmp);
			
			tmp=copyMap(map);
			checkLeft(tmp,obj.x,obj.y);
			checkUp(tmp,obj.x,obj.y);
			dfs(depth+1,tmp);
			break;
		case 4:
			tmp=copyMap(map);
			checkLeft(tmp,obj.x,obj.y);
			checkUp(tmp,obj.x,obj.y);
			checkRight(tmp,obj.x,obj.y);
			dfs(depth+1,tmp);
			
			tmp=copyMap(map);
			checkRight(tmp,obj.x,obj.y);
			checkDown(tmp,obj.x,obj.y);
			checkLeft(tmp,obj.x,obj.y);
			dfs(depth+1,tmp);
			
			tmp=copyMap(map);
			checkUp(tmp,obj.x,obj.y);
			checkDown(tmp,obj.x,obj.y);
			checkLeft(tmp,obj.x,obj.y);
			dfs(depth+1,tmp);
						
			tmp=copyMap(map);
			checkUp(tmp,obj.x,obj.y);
			checkDown(tmp,obj.x,obj.y);
			checkRight(tmp,obj.x,obj.y);
			dfs(depth+1,tmp);
			break;
		case 5:
			tmp=copyMap(map);
			checkRight(tmp,obj.x,obj.y);
			checkDown(tmp,obj.x,obj.y);
			checkLeft(tmp,obj.x,obj.y);
			checkUp(tmp,obj.x,obj.y);
			dfs(depth+1,tmp);
			break;
		}
	}
	
	public static int[][] copyMap(int[][] map) {
		int[][] tmp=new int[N][M];
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				tmp[i][j]=map[i][j];
			}
		}
		return tmp;
	}
	
	public static void checkRight(int[][] map,int x,int y) {
		for(int i=x+1;i<M;i++) {
			if(map[y][i]==6) return;
			if(map[y][i]==0) map[y][i]=-1;
		}
	}
	
	public static void checkLeft(int[][] map,int x,int y) {
		for(int i=x-1;i>=0;i--) {
			if(map[y][i]==6) return;
			if(map[y][i]==0) map[y][i]=-1;
		}
	}
	
	public static void checkUp(int[][] map,int x,int y) {
		for(int i=y-1;i>=0;i--) {
			if(map[i][x]==6) return;
			if(map[i][x]==0) map[i][x]=-1;
		}
	}
	
	public static void checkDown(int[][] map,int x,int y) {
		for(int i=y+1;i<N;i++) {
			if(map[i][x]==6) return;
			if(map[i][x]==0) map[i][x]=-1;
		}
	}
}