[백준] 1799 : 비숍

 

문제

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

 

 

 

 

입출력

5
1 1 0 1 1
0 1 0 0 0
1 0 1 0 1
1 0 0 0 0
1 0 1 1 1

 

7

---

아이디어

 

- 백트래킹 : 많은 경우의 수를 어떻게 줄일 것인가

 

1) 체스판에서 흑/백 칸을 나누어 백트래킹 

2) 대각선 x - y, x + y 충돌 체크 : 대각선이 겹치지 않도록 가지치기 

3) 최적의 비숍 배치를 구한 후, 합산 : 흑색 칸에서 최대 비숍 수 + 백색 칸에서 최대 비숍 수 

코드 

- 정답 

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

public class Main {
	static int N;
	static int[][] box;
	static List<int[]> blacks;
	static List<int[]> whites;

	static boolean[] twoFour;
	static boolean[] oneThree;

	static int EMPTY = 0, BISOP = 2;
	static int maxBisopCnt;
	static int maxBlack, maxWhite;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		blacks = new ArrayList<>();
		whites = new ArrayList<>();
		N = Integer.parseInt(br.readLine());
		box = new int[N][N];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				box[i][j] = Integer.parseInt(st.nextToken());
				if (box[i][j] == 1) { // 비숍을 놓을 수 있는 곳
					if ((i + j) % 2 == 0) { // 놓을 수 있는 비숍의 위치를 
						blacks.add(new int[] { i, j }); // 검은색 
					} else {
						whites.add(new int[] { i, j }); // 흰색 으로 나눈다 
					}
				}
				// 비숍을 놓을 수 없는 곳 : 0
			}
		}

		twoFour = new boolean[N * 2];
		oneThree = new boolean[N * 2];

		back(blacks, 0, 0); // 검은색끼리
		maxBlack = maxBisopCnt;

		maxBisopCnt = 0;
		back(whites, 0, 0); // 흰색끼리 
		maxWhite = maxBisopCnt;
		
        // 검은색 위치에 있는 말이 흰색 위치에 있는 말에 영향을 주지 않음
		System.out.println(maxBlack + maxWhite); // 독립적인 사건이므로

	}

	static void back(List<int[]> positions, int idx, int cnt) {
		if (idx >= positions.size()) {
			maxBisopCnt = Math.max(maxBisopCnt, cnt);
			return;
		}
		int x = positions.get(idx)[0];
		int y = positions.get(idx)[1];

		if (!twoFour[x - y + N] && !oneThree[x + y]) { // 현재 위치에 비숍을 놓는 경우
			twoFour[x - y + N] = true;
			oneThree[x + y] = true;

			back(positions, idx + 1, cnt + 1); // 개수(cnt) + 1

			twoFour[x - y + N] = false;
			oneThree[x + y] = false;
		}
		back(positions, idx + 1, cnt); // 비숍을 놓지않는 경우
	}

	static boolean inRange(int x, int y) {
		return x >= 0 && x < N && y >= 0 && y < N;
	}

}

 

- 시간 초과 

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

public class Main {
	static int N;
	static int[][] box;
	static List<int[]> emptys;
	static boolean[] selected;

	static int EMPTY = 0, BISOP = 2;
	static int maxBisopCnt = Integer.MIN_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		emptys = new ArrayList<>();
		N = Integer.parseInt(br.readLine());
		box = new int[N][N];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				box[i][j] = Integer.parseInt(st.nextToken());
				if (box[i][j] == 1) { // 비숍을 놓을 수 있는 곳
					emptys.add(new int[] { i, j });
				}
				// 비숍을 놓을 수 없는 곳 : 0
			}
		}
		selected = new boolean[emptys.size()];
		back(0);
		System.out.println(maxBisopCnt);
	}

	static void back(int cnt) {
		if (cnt == emptys.size()) {

			int bisopCnt = 0;
			for (int i = 0; i < emptys.size(); i++) {
				if (selected[i]) {
					int x = emptys.get(i)[0];
					int y = emptys.get(i)[1];
					box[x][y] = BISOP;
					bisopCnt += 1;
				}
			}

			boolean canCatch = false;
			for (int i = 0; i < emptys.size(); i++) {
				if (selected[i]) {
					int x = emptys.get(i)[0];
					int y = emptys.get(i)[1];
					if (isBisopInDiagonal(x, y)) {
						canCatch = true;
						break;
					}
				}
			}

			if (!canCatch) {
				maxBisopCnt = Math.max(maxBisopCnt, bisopCnt);
			}

			for (int i = 0; i < emptys.size(); i++) {
				if (selected[i]) {
					int x = emptys.get(i)[0];
					int y = emptys.get(i)[1];
					box[x][y] = EMPTY;
				}
			}

			return;
		}
		selected[cnt] = true;
		back(cnt + 1);
		selected[cnt] = false;
		back(cnt + 1);

	}

	static int[][] way = { { -1, -1 }, { -1, 1 }, { 1, -1 }, { 1, 1 } };

	static boolean isBisopInDiagonal(int x, int y) {
		boolean isInDiagonal = false;
		for (int w = 0; w < 4; w++) {
			int r = x, c = y;
			while (true) {
				int nx = r + way[w][0];
				int ny = c + way[w][1];
				if (!inRange(nx, ny))
					break;
				if (box[nx][ny] == BISOP) {
					isInDiagonal = true;
					break;
				}
				r = nx;
				c = ny;
			}
			if (isInDiagonal) {
				break;
			}
		}
		return isInDiagonal;
	}

	static boolean inRange(int x, int y) {
		return x >= 0 && x < N && y >= 0 && y < N;
	}

}