[백준][ 자바 ][ 15683 ] 감시

하... dfs엔 약해서 좀 오래걸린문제

다른 사람들 코드를 보고 참조해도

이 문제는 뭔가 까탈스러운게 많아서 힘들었다.

완전탐색을 하라고 문제에서 거의 알려주다싶히 하는데

처음엔 당최 어떻게 할지 감이 안왔다.

 모든 가짓수를 다 알아야하는데

각 cctv마다 보는 방향이 달라서 일일히 구현해줘야한다( 이게 엄청 귀찮았음 )

그리고 모든 경우를 탐색해보면 된다..

완전탐색 간단한 문제부터 다시 풀어봐야할것같다,ㅠ

package back;

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

class CCTV {
	int x; 
	int y;
	int cctvNumber;
	CCTV(int y, int x, int cctvNumber){
		this.y = y;
		this.x = x;
		this.cctvNumber = cctvNumber;
	}
}
public class backjoon_Main_15683 {
	static int[][] MAP = new int[9][9];
	static int CCTV;
	static int M;
	static int N;
	static int MINIMUM= 999999;
	static ArrayList cctvArr = 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() );
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int idx = 0;
			while(st.hasMoreTokens()) {
				MAP[i][idx] = Integer.parseInt( st.nextToken() );
				if(MAP[i][idx] != 6 && MAP[i][idx] != 0) {
					cctvArr.add(new CCTV(i, idx, MAP[i][idx]));
				}
				idx++;
			}
		}
		
		
		view(0, MAP);
		System.out.println(MINIMUM);
		
	}

	public static void copyArray(int[][] target, int[][] beforeMap ) {
		for(int i = 0 ; i < N; i++) {
			for(int j =0; j < M; j++) {
				target[i][j] = beforeMap[i][j];
			}
		}
		

	}
	public static void view( int index, int[][] beforeMap ) {
		int[][] visited = new int[N+1][M+1];
		
		if( index == cctvArr.size()) {
			/* 최소 갯수 구하기 */
			int cnt = 0;
			for(int i = 0 ; i < N; i++) {
				for(int j = 0; j < M; j++) {
					if( beforeMap[i][j] == 0) {
						cnt ++;
					}
				}
			}
			if( MINIMUM > cnt ){
				MINIMUM = cnt;
				//System.out.println("MINIMUM "+ MINIMUM);
				//printVisited(beforeMap);
			}
			return;
		}
		
		
		CCTV cctv = cctvArr.get(index);
		int x = cctv.x;
		int y = cctv.y;
		int cctvNumber = cctv.cctvNumber;
//		System.out.println("index " + index);
//		System.out.println("cctvNumber " + cctvNumber);
//		System.out.println("X " + x + " Y" + y);
//		
		if( cctvNumber == 1 ) {
			for(int number = 0; number < 4; number++) { //rotate 와 관련있음
				copyArray(visited, beforeMap);
				
				search(number, y ,x ,visited);
				view(index +1, visited);
			}
		} 
		
		if( cctvNumber == 2 ) {
			//상하 좌우 
			for(int number = 0; number < 2; number++ ) { //rotate 와 관련있음
				copyArray(visited, beforeMap);
				search(number , y ,x ,visited);
				search(number + 2 , y ,x ,visited);
				view(index +1, visited );
			}
		}
		
		if( cctvNumber == 3 ) {
			//상하 좌우 
			for(int number = 0; number < 4; number++) { //rotate 와 관련있음
				copyArray(visited, beforeMap);
				search(number, y ,x ,visited);
				search(( number + 1) % 4 , y ,x ,visited);
				
				view(index + 1 ,visited);
			}
		}
		
		if( cctvNumber == 4 ) {
			//상하 좌우 
			for(int number = 0; number < 4; number++) { //rotate 와 관련있음
				if(number == 0 ) {
					copyArray(visited, beforeMap);
					search(0, y ,x ,visited);
					search(1, y ,x ,visited);	
					search(3, y ,x ,visited);	
					view(index + 1 ,visited);
				}
				if(number == 1 ) {
					copyArray(visited, beforeMap);
					search(0, y ,x ,visited);
					search(1, y ,x ,visited);	
					search(2, y ,x ,visited);	
					view(index + 1 ,visited);
				}
				if(number == 2 ) {
					copyArray(visited, beforeMap);
					search(1, y ,x ,visited);
					search(2, y ,x ,visited);	
					search(3, y ,x ,visited);	
					view(index + 1,visited );
				}
				if(number == 3 ) {
					copyArray(visited, beforeMap);
					search(0, y ,x ,visited);
					search(2, y ,x ,visited);	
					search(3, y ,x ,visited);	
					view(index + 1,visited );
				}
			}
		}

		if( cctvNumber == 5 ) {
			//System.out.println("Dd");
			copyArray(visited, beforeMap);
			search(0, y ,x ,visited);
	
			search(1, y ,x ,visited);	
	
			search(2, y ,x ,visited);
		
			search(3, y ,x ,visited);
		
			view(index + 1,visited);
		
		}
	
		//System.out.println();
		
	}
	public static void printVisited(int[][] visited) {
		for(int i = 0 ; i < N; i++) {
			for(int j =0; j = 0; yy--) {
				if(MAP[yy][x] == 6) break;
				visited[yy][x] = 9; 
			}
			
		}
		/* 우  */
		if( number == 1) { 
			for(int xx = x; xx < M; xx++) {
				if(MAP[y][xx] == 6) break;
				visited[y][xx] = 9; 
			}
			
		}
		/* 하  */
		if( number == 2) { 
			for(int yy = y; yy < N; yy++) {
				if(MAP[yy][x] == 6) break;
				visited[yy][x] = 9; 
			}
		}
		/* 좌 */
		if( number == 3) { 
			for(int xx = x; xx >= 0; xx--) {
				if(MAP[y][xx] == 6) break;
				visited[y][xx] = 9; 
			}
		}
	}
	

}