[백준, 1799, 자바] 비숍

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

1799번: 비숍

1. 문제 핵심

1. 비숍은 대각선으로만 움직일 수 있다.

2. 체스판 가로, 세로는 열 개 이하의 칸을 가진다.

3. ↓ 핵심

흰 색 칸에 속하는 비숍은 검은 색 칸의 비숍에게 간섭을 못하고, 검은 색 칸의 비숍은 흰 색 칸의 비숍에게 간섭하지 못한다. (중요)

2. 문제 접근

1. 백트래킹으로 비숍을 놓을 수 있는 각 칸마다 해당 칸의 좌상 대각선, 우상 대각선에 다른 비숍이 있는지 확인한다.
좌상, 우상 대각선 모든 칸에 하나의 비숍이라도 존재한다면 해당 칸은 비숍을 놓지않고 비숍이 없다면 현재 칸에 비숍을 놓는다.

2. 한 번 비숍을 놓았다면 비숍을 놓지 않았을 때의 경우도 확인해준다.

3. ↓ 문제 핵심 3번 개념 참고 후

서로 간섭하지 못하기 때문에 백트래킹을 흰색 칸, 검은 색 나눠주어 진행해주었다.

 

3. 그림 설명

예제 입력 1은 다음과 같다.

예제 1번

작은 규모의 체스판에서는 모든 칸을 노드로 두고 백트래킹을 해도 빠르게 출력이 가능하지만 10 * 10칸 모두 비숍을 놓을 수 있는 체스판에선 시간 초과가 난다.

 

따라서 비숍의 특성인 대각선으로만 움직일 수 있다는 점을 활용해서 서로 간섭하지 못하는 흰색 칸 비숍과 검은색 칸 비숍을 각각 백트래킹해준다.

 

 

자바 코드

import java.io.DataInputStream;
import java.io.IOException;

public class Main {
	static class Reader {
		int bfs = 1 << 16;
		byte[] buffer = new byte[bfs];
		int bufferPos = 0, bufferState = 0;
		DataInputStream dis = new DataInputStream(System.in);

		byte read() throws IOException {
			if (bufferPos == bufferState) {
				bufferState = dis.read(buffer, bufferPos = 0, bfs);

				if (bufferState == -1)
					buffer[0] = -1;
			}
			return buffer[bufferPos++];

		}

		int nextInt() throws IOException {
			int rtn = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do
				rtn = rtn * 10 + c - '0';
			while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -rtn;
			return rtn;
		}
	}

	static int[][] bd, bd2, eachV;
	static int N, row, col, Zmax = 0, Omax = 0, avil = 0, tmprow, tmpcol, next;

	// 위로 비숍 존재하는지 검사
	static boolean isVishop(int row, int col) {
		// mark top to bottom
		tmprow = row + 1;
		tmpcol = col - 1;
		// left down mark
		while (tmprow < N && tmpcol >= 0) {
			if (bd[tmprow][tmpcol] == 1)
				bd[tmprow][tmpcol] = 2;
			tmprow += 1;
			tmpcol -= 1;
		}
		tmprow = row + 1;
		tmpcol = col + 1;
		// right down mark
		while (tmprow < N && tmpcol < N) {
			if (bd[tmprow][tmpcol] == 1)
				bd[tmprow][tmpcol] = 2;
			tmprow += 1;
			tmpcol += 1;
		}
		return true;
	}

	static boolean isSet(int row, int col, int who) {

		
		
		if (who == 0) {
			// check can visit
			tmprow = row - 1;
			tmpcol = col - 1;
			// left top mark
			while (tmprow >= 0 && tmpcol >= 0) {
				if (bd[tmprow][tmpcol] == 2)
					return false;
				tmprow -= 1;
				tmpcol -= 1;
			}

			tmprow = row - 1;
			tmpcol = col + 1;
			// right top mark
			while (tmprow >= 0 && tmpcol < N) {
				if (bd[tmprow][tmpcol] == 2)
					return false;
				tmprow -= 1;
				tmpcol += 1;
			}
			bd[row][col] = 2;
		}
			
		else {
			// check can visit
			tmprow = row - 1;
			tmpcol = col - 1;
			// left top mark
			while (tmprow >= 0 && tmpcol >= 0) {
				if (bd2[tmprow][tmpcol] == 2)
					return false;
				tmprow -= 1;
				tmpcol -= 1;
			}

			tmprow = row - 1;
			tmpcol = col + 1;
			// right top mark
			while (tmprow >= 0 && tmpcol < N) {
				if (bd2[tmprow][tmpcol] == 2)
					return false;
				tmprow -= 1;
				tmpcol += 1;
			}
			bd2[row][col] = 2;
		}
			
		return true;
	}

	static void rollback(int row, int col) {
		bd[row][col] = 1;

		// check can visit
		tmprow = row - 1;
		tmpcol = col - 1;
		// left down mark
		while (tmprow >= 0 && tmpcol >= 0) {
			if (bd[tmprow][tmpcol] == 2)
				bd[tmprow][tmpcol] = 1;
			tmprow -= 1;
			tmpcol -= 1;
		}
		tmprow = row - 1;
		tmpcol = col + 1;
		// right down mark
		while (tmprow >= 0 && tmpcol < N) {
			if (bd[tmprow][tmpcol] == 2)
				bd[tmprow][tmpcol] = 1;
			tmprow -= 1;
			tmpcol += 1;
		}

		// check can visit
		tmprow = row + 1;
		tmpcol = col - 1;
		// left down mark
		while (tmprow < N && tmpcol >= 0) {
			if (bd[tmprow][tmpcol] == 2)
				bd[tmprow][tmpcol] = 1;
			tmprow += 1;
			tmpcol -= 1;
		}
		tmprow = row + 1;
		tmpcol = col + 1;
		// right down mark
		while (tmprow < N && tmpcol < N) {
			if (bd[tmprow][tmpcol] == 2)
				bd[tmprow][tmpcol] = 1;
			tmprow += 1;
			tmpcol += 1;
		}
	}

	// N*N개 반복
	static void dfs1(int crnt, int cnt) {
		if (crnt >= N * N) {
			Zmax = Math.max(cnt, Zmax);
			return;
		}

		int row = crnt / N;
		int col = crnt % N;

		if (N % 2 == 0 && row % 2 == 1) {
			col++;
		}

		// 현재 자리 가능 && can LT, RT
		if (bd[row][col] == 1 && isSet(row, col, 0)) {
			dfs1(crnt + 2, cnt + 1);
			bd[row][col] = 1;
		}

		dfs1(crnt + 2, cnt);
	}

	static void dfs2(int crnt, int cnt) {

		if (crnt >= N * N) {
			Omax = Math.max(cnt, Omax);
			return;
		}

		int row = crnt / N;
		int col = crnt % N;
		// N이 짝수, 홀수번째는 홀수행마다 -1
		if (N % 2 == 0 && row % 2 == 1) {
			col--;
		}

		// 현재 자리 가능 && can LT, RT
		if (bd2[row][col] == 1 && isSet(row, col, 1)) {
			dfs2(crnt + 2, cnt + 1);
			bd2[row][col] = 1;
		}

		dfs2(crnt + 2, cnt);

	}

	// 좌하, 우하 모두 2로 변경
	public static void main(String[] args) throws IOException {
		Reader br = new Reader();

		N = br.nextInt();

		bd = new int[N][N];
		bd2 = new int[N][N];
		eachV = new int[N * N][2];
		next = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				bd[i][j] = br.nextInt();
				bd2[i][j] = bd[i][j];
			}
		}
		dfs1(0, 0);
		if (N != 1) {
			dfs2(1, 0);
		}

		System.out.println(Zmax + Omax);
	}
}