[백준] 1799번 : 비숍 - 자바(JAVA)

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

1799번: 비숍

 

문제 해석

서양 장기인 체스에 대각선 방향으로 움직일 수 있는 비숍이 있습니다.

 

비숍의 위치라 B라고 했을 때 다음 그림처럼 움직일 수 있습니다.

B는 비숍의 위치(O는 잡을 수 있는 말들)

이때 색칠된 부분에는 비숍을 놓을 수 없지만 지나갈 수는 있다고 하겠습니다.

이와 같은 체스판에 서로가 서로가 잡을 수 없는 비숍을 놓는다면 최대 7개의 비숍을 넣을 수 있습니다.

색칠된 부분에는 B를 놓을 수 없지만 지나갈 순 있음

비숍의 최대 개수를 구하는 프로그램을 작성하세요.

 

체스판의 크기는 10 이하의 자연수, 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄씩 주어집니다.

 

비숍을 놓을 수 있으면 1 , 없으면 0

 

문제 풀이 전 설계

체스판의 크기가 10이하인 점, 시간 제판이 10초인 점을 감안한다면 완전 탐색 DFS를 통해 문제를 해결할 수 있을 것 같습니다.

 

 

1. 비숍을 놓을 수 있는 곳인 1에 차례대로 비숍을 채워넣자(이때 가상의 보드를 만들어서 비숍을 놓을 수 없는 공간들을 마킹)

2. 불가능하다면 다음칸을 탐색하고 더이상 놓을 수 없다면 재귀 함수 return을 통해 찾는다.

3. 이 과정속에서 최대로 놓을 수 있는 비숍을 갱신해나간다.

 

문제 풀이 하면서

문제의 핵심은 비숍의 이동경로를 나누어 생각하는 것 같습니다.

비숍의 이동 경로

Black	White	Black	White	Black
White	Black	White	Black	White
Black	White	Black	White	Black
White	Black	White	Black	White
Black	White	Black	White	Black

BLACK에 놓인 비숍은 BLACK으로만 이동할 수 있으며 WHITE에 놓인 비숍은 WHITE로만 이동할 수 있습니다.

따라서 NxN의 체스판을 2개의 체스판으로 나누어 탐색하는 방법을 취할 수 있습니다.

 

 

코드

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

public class Main_1799_비숍 {
    static int N;
    static int[] res;
    static int[][] board;
    static boolean[][] visited, isBlack;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        res = new int[2];
        board = new int[N][N];
        visited = new boolean[N][N];
        isBlack = new boolean[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());
                isBlack[i][j] = (i % 2 == 0 && j % 2 == 0) || (i % 2 == 1 && j % 2 == 1);
            }
        }

        dfs(0,true,0); // black 칸의 비숍
        dfs(0,false,0); // white 칸의 비숍
        System.out.println(res[0] + res[1]);
    }

    static void dfs(int index, boolean black, int cnt) {

        for (int i = index; i < N * N; i++) {
            int x = i / N;
            int y = i % N;

            if (board[x][y] == 0 || isBlack[x][y] != black || !check(x, y))
                continue;

            visited[x][y] = true;
            dfs(i + 1, black, cnt + 1);
            visited[x][y] = false;
        }

        res[black ? 0 : 1] = Math.max(res[black ? 0 : 1], cnt);
    }

    // 현재 위치  +  대각선 체크
    static boolean check(int x, int y) {
        int[] dx = {-1,-1};
        int[] dy = {-1,1};

        for (int i = 0; i < 2; i++){
            int nx = x;
            int ny = y;
            while (true) {
                if (0 > nx || nx >= N || 0 > ny || ny >= N)
                    break;
                if (visited[nx][ny])
                    return false;

                nx += dx[i];
                ny += dy[i];
            }
        }
        return true;
    }
}