BOJ_1799_비숍 (Java)

[Gold I] 비숍 - 1799

문제 링크

성능 요약

메모리: 18572 KB, 시간: 276 ms

분류

백트래킹

제출 일자

2024년 9월 9일 01:33:43

문제 설명

서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. < 그림 1 >과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.

< 그림 1 >

그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. < 그림 2 >에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 < 그림 3 >과 같이 최대 7개의 비숍을 놓을 수 있다. 색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다.

< 그림 2 >

< 그림 3 >

정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다. 체스판의 크기와 체스판 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 주어질 때, 서로가 서로를 잡을 수 없는 위치에 놓을 수 있는 비숍의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 한 줄씩 주어진다. 비숍을 놓을 수 있는 곳에는 1, 비숍을 놓을 수 없는 곳에는 0이 빈칸을 사이에 두고 주어진다.

출력

첫째 줄에 주어진 체스판 위에 놓을 수 있는 비숍의 최대 개수를 출력한다.

문제 풀이

검은 칸과 흰 칸을 나누어 계산 -> 절대 겹치지 않으므로 첫 검은칸 dfs, 첫 흰칸 dfs 이때, 각 칸에서 대각선으로 쭉 진행, 비숍 놓은칸은 2로.

코드

/**
 * Author : nowalex322, Kim Hyeonjae
 */

import java.io.*;
import java.util.*;

public class Main {
    public static BufferedReader br;
    public static BufferedWriter bw;
    public static int N, tmp, ans;
    public static int[][] board;
    public static int[] dr = {-1, 1, 1, -1};
    public static int[] dc = {1, 1, -1, -1};
    public static void main(String[] args) throws IOException {
//    	br = new BufferedReader(new InputStreamReader(System.in));
    	br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
    	bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	N = Integer.parseInt(br.readLine());
    	board = new int[N][N];
    	
    	for (int i = 0; i < N; i++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		for (int j = 0; j < N; j++) {
    			board[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	//첫째칸부터(흰칸) DFS
        dfs(0, 0);
        ans += tmp;
        
        tmp = 0;
        //두번째칸부터(흑칸) DFS
        dfs(1, 0);
        ans += tmp;
        
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    public static boolean isPuttable(int i, int j) {
        for (int k = 0; k < 4; k++) {
        	// 대각선으로 늘어날 길이 n
            int n = 1;
            while(true) {
                int r = i + n * dr[k];
                int c = j + n * dc[k];
                // 경계조건 밖일때
                if (r < 0 || c < 0 || r >= N || c >= N) break;
                    
                // 비숍 놓아져 있는경우
                if (board[r][c] == 2) return false;
                n++;
            }
        }
        return true;
    }

    /**
     * 이동할 칸 계산
     * 판 길이 홀수x홀수면 2씩증가, 짝수면 흑백 계산해서 증가
     * @param i
     * @return
     */
    public static int calNext(int i) {
        //크기가 홀 수일 경우 -> 2증가
        if (N % 2 == 1) return 2;
        
        //크기가 짝수일 경우
        if (i % N == N-1) return 1;
        else if (i % N == N-2) return 3;
        else return 2;
    }

    public static void dfs(int i, int cnt) {
        if (i >= N*N) {
            tmp = Math.max(tmp, cnt);
            return;
        }
        int c = i % N;
        int r = i / N;
        int next = calNext(i);

        // 둘 수 없는 곳일 경우
        if (board[r][c] == 0) {
            dfs(i + next, cnt);
            return;
        }

        // 둘 수 있는 곳일 경우
        if (isPuttable(r, c)) {
            board[r][c] = 2;
            dfs(i+next, cnt+1);
            board[r][c] = 1;
        }
        // 그냥 안두는 케이스
        dfs(i+next, cnt);
    }

}