백준_비숍_1799

문제 링크

조건

•  N  : 체스판 크기, 1~10 이하 자연수
• 비숍은 사방 대각선으로 공격 가능

 

접근 방법

• 체스판의 검은 영역 과 흰 영역 을 분리해 생각
  • 큰 덩어리를 둘로 분리해 작은 덩어리 두 번 계산
• 시간복잡도
  • 영역을 분리하지 않은 경우 : O(2 ^ (N*N)) => 각각의 체스칸마다(N*N개) 비숍을 놓을 지 말지 선택(2가지)
  • 영역을 분리한 경우 : O(2 ^ (N/2 * N/2)) => 각각의 체스칸마다(N/2*N/2개) 비숍을 놓을 지 말지 선택(2가지) * 2(흰 영역, 검은 영역 두 번 계산)

 

솔루션

public class Main_1799_비숍 {

	static int N, size, max;//map N*N
	static int[][] map;//체스판
	static int[] dr = {-1,-1,1,1};//대각선
	static int[] dc = {-1,1,-1,1};
	static List<int[]> black, white;//비숍 놓을 수 있는 칸 정보
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine().trim());
		
		map = new int[N][N];
		black = new ArrayList<int[]>();
		white = new ArrayList<int[]>();
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine().trim(), " ");
			for(int j = 0; j < N; j++) {
				if(st.nextToken().charAt(0) == '1') {//빈칸
					if((i+j) % 2 == 0) black.add(new int[] {i,j});
					else white.add(new int[] {i,j});
					map[i][j] = 0;
				}else {//비숍 놓을 수 X
					map[i][j] = -1;
				}
			}
		}
		
		//체스 검은칸 개수 => O(2 ^ (N/2 * N/2))
		size = black.size();//빈칸 개수
		dfs(0,0, black);
		int black = max;
		
		//체스 흰칸 개수 => O(2 ^ (N/2 * N/2))
		size = white.size();
		max = 0;
		dfs(0,0, white);
		
		System.out.println(black + max);
		
		
	}
	
    //empty 리스트 인덱스, 이제까지 비숍 놓은 개수, 빈칸 영역
	private static void dfs(int idx, int cnt, List<int[]> empty) {
		if(max < cnt) max = cnt;
		
		int[] point;
		int r,c,nr,nc;
		for(int i = idx; i < size; i++) {
			point = empty.get(i);
			r = point[0];
			c = point[1];
			
			if(map[r][c] > 0) {//다른 곳에 놓은 비숍의 공격 범위에 있는 경우
				continue;
			}
			
			map[r][c] = 1;//비숍 놓음
			//비숍 공격범위 체크
			for(int k = 0; k < 4; k++) {
				nr = r + dr[k];
				nc = c + dc[k];
				while(nr > -1 && nr < N && nc > -1 && nc < N) {
					if(map[nr][nc] > -1) {//-1이면 원래 못놓는 곳
						map[nr][nc]++;
					}
					
					nr += dr[k];
					nc += dc[k];
				}
			}
				
			dfs(i+1, cnt+1, empty);
			map[r][c] = 0;//놓았던 비숍 지움
			//비숍 공격범위 지우기
			for(int k = 0; k < 4; k++) {
				nr = r + dr[k];
				nc = c + dc[k];
				while(nr > -1 && nr < N && nc > -1 && nc < N) {
					if(map[nr][nc] > -1) {//-1이면 원래 못놓는 곳
						map[nr][nc]--;
					}
					
					nr += dr[k];
					nc += dc[k];
				}
			}
			
		}
	}
	
}

 

리뷰

• 처음에 체스판의 검은 영역 과 흰 영역 을 분리해 생각하지 못함(어떻게 생각해냄 이런거를..?)
• 같은 로직을 위와같이 절반으로 나누면 시간복잡도가 훨씬 줄어듦..!!