BJ G2 1799 비숍

BJ G2 1799 비숍

 

 

문제링크

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

1799번: 비숍

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://www.youtube.com/watch?v=oBMlSKTGPKs

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l2;

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

/**
 * @author itsmeyjc
 * @since 2020. 4. 20.
 * @see https://www.acmicpc.net/problem/1799
 * @mem 16724
 * @time 280
 * @caution 모든 칸을 기준으로 탐색할 경우 N*N칸에 모두 2가지 경우를 체크해야 하므로 O(2^(N*N)) 즉 O(2^100)의 어머어마한 시간 복잡도를
 * 갖는다.
 * 하지만 검정과 흰색을 기준으로 탐색한다면 O(2^(N/2*N/2))*2 = O(2^25)*2 = 6700만의 시간 복잡도가 된다.
 */
public class BJ_G2_1799_비숍 {
    static StringBuilder sb = new StringBuilder();

    // 흰 칸을 기준으로 했을 경우와 검은 칸을 기준으로 했을 때 둘로 나눠서 관리
    static int[] answer = new int[2];

    static int N;
    static int[][] map;
    static boolean[][] visited;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new StringReader(src));

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new boolean[N][N];

        StringTokenizer tokens = null;
        for (int r = 0; r < N; r++) {
            tokens = new StringTokenizer(br.readLine());
            for (int c = 0; c < N; c++) {
                map[r][c] = Integer.parseInt(tokens.nextToken());
            }
        }

        dfs(0, 0, 0, 'W');
        dfs(0, 1, 0, 'B');
        System.out.println(answer[0] + answer[1]);
    }

    public static void dfs(int row, int col, int cnt, char type) {
        // col이 N을 넘어가면 줄을 바꾸는데 다음줄에서의 col은 type에 따라 상황이 달라진다.
        if (col >= N) {
            row = row + 1;
            // White 인 경우 : 짝수번째 행의 경우는 0부터, 홀수번째 행은 1부터
            if (type == 'W') {
                col = row % 2 == 0 ? 0 : 1;
            }
            // Black 인 경우 : 짝수번째 행의 경우는 1부터, 홀수번째 행은 0부터
            else {
                col = row % 2 == 0 ? 1 : 0;
            }
        }

        // 마지막 줄에 왔으면 그만 - type에 따라 답 저장
        if (row == N) {
            if (type == 'W') {
                answer[0] = Math.max(answer[0], cnt);
            } else {
                answer[1] = Math.max(answer[1], cnt);
            }
            return;
        }

        // 지도가 1이어서 놓을 수 있는 경우는 놔보고 유망한지에 따라 다음 재귀를 호출한다.
        if (map[row][col] == 1) {
            visited[row][col] = true;
            if (isPromising(row, col)) {
                dfs(row, col + 2, cnt + 1, type);
            }
            visited[row][col] = false;
        }
        // 아니면 다음 기회
        dfs(row, col + 2, cnt, type);
    }

    public static boolean isPromising(int currentRow, int currentCol) {
        boolean result = true;
        // 위쪽 대각선 지점을 누군가 점유하고 있으면 아웃
        for (int r = currentRow - 1, t = 1; r >= 0; r--, t++) {
            if ((currentCol - t >= 0 && visited[r][currentCol - t]) || (currentCol + t < N && visited[r][currentCol + t])) {
                return false;
            }
        }
        return result;
    }


    static String src = "9\r\n" +
                        "1 1 1 1 1 1 1 1 1\r\n" +
                        "1 1 1 1 1 1 1 1 1\r\n" +
                        "1 1 1 1 1 1 1 1 1\r\n" +
                        "1 1 1 1 1 1 1 1 1\r\n" +
                        "1 1 1 1 1 1 1 1 1\r\n" +
                        "1 1 1 1 1 1 1 1 1\r\n" +
                        "1 1 1 1 1 1 1 1 1\r\n" +
                        "1 1 1 1 1 1 1 1 1\r\n" +
                        "1 1 1 1 1 1 1 1 1";
}