백준 1799 - 비숍 (Java)

문제

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

< 그림 1 >

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

< 그림 2 >

< 그림 3 >

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

입력

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

출력

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

예제 입력 1 복사

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

예제 출력 1 복사

7

 

풀이

메모리초과 시간초과 둘 다 봤다.

처음엔 백트래킹 만들고 배열 계속 복사해서 넘겨주니까 메모리초과,

복사 빼니까 시간초과

?

검색해보니까 두 개로 나누라고 나온다. 체스 판에서 흰색과 검은색에 있는 비숍은 서로간에 간섭을 못한단다.

아?!

체스란걸 전혀 생각 안했다.

검은색과 하얀색 두개로 나눠서 백트래킹 진행. 둘의 합을 출력하면 된다.

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

public class BJ_1799_비숍 {
    static int N;
    static int result;
    static int black;
    static int white;

    static int[][] map;
    static int[][] chess;
    static int[][] deltas = {{-1,-1},{-1,1},{1,-1},{1,1}};
    static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        visited = new boolean[N][N];
        for(int i=0; i<N; i++)
        {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++)
            {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        chess = new int[N][N];
        int count = 0;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                chess[i][j] = (i+j) % 2;
            }
        }
        dfs(0,0,chess[0][0],0);
        dfs(0,1,chess[0][1],0);
        result = black+white;
        System.out.println(result);
    }

    public static void dfs(int y, int x, int color ,int count) {
        if(y >= N) {
            if(color == 0) {
                black = Math.max(black, count);
            }
            else {
                white = Math.max(white, count);
            }
            return;
        }

        int nx = x + 2;
        int ny = y;

        if(nx >= N) {
            ny++;
            if(ny < N) {
                if(chess[ny][0] == color) {
                    nx = 0;
                }
                else {
                    nx = 1;
                }
            }
        }

        if(map[y][x] == 0) {
            dfs(ny, nx, color, count);
            return;
        }

        if(check(y,x)) {
            visited[y][x] = true;
            dfs(ny, nx, color, count+1);
            visited[y][x] = false;
        }

        dfs(ny, nx, color, count);
    }

    public static boolean check(int x,int y)
    {
        int goCnt = 0;
        for(int dir=0; dir<4; dir++)
        {
            if(go(x,y,dir)) goCnt++;
        }
        if(goCnt<4) return false;
        return true;
    }

    public static boolean go(int x, int y, int dir)
    {
        int nx = x;
        int ny = y;
        while(true)
        {
            nx+=deltas[dir][0];
            ny+=deltas[dir][1];
            if(nx<0||N<=nx || ny<0||N<=ny) break;
            if(visited[nx][ny]) return false;
        }
        return true;
    }
}