[백준, BOJ 1799] 비숍 (java)

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

메모리: 15,996 KB , 시간: 192 ms

사용 알고리즘: 백트래킹

728x90

---

일단 이 문제에서 내가 생각해 낸 아이디어는,

체스판에서 왼쪽 위 -> 오른쪽 아래로 내려오는 라인들을 그었을 때, 각 라인 위에 위치한 비숍들은 다른 라인에 영향을 줄 수 없다.

마찬가지로 오른쪽 위부터 왼쪽 아래로 내려오는 라인들을 그었을 때, 각 라인 위에 위치한 비숍들은 다른 라인에 영향을 줄 수 없다.

 

이 아이디어를 가지고 오른쪽 위 -> 왼쪽 아래로 내려오는 라인들을 해당 라인에서 비숍을 하나 고르고 다른 라인에서 비숍을 고르러 가는 방법으로 백트래킹 했다.

(비숍을 하나 골랐을 때, 왼쪽 위 -> 오른쪽 아래 라인에 이미 비숍이 있으면 놓을 수 없다.)

그런데 이 방법의 경우 $N^{2*N-1}$의 시간 복잡도가 걸린다.

 

해결 방법이 생각 안나 블로그들을 찾아보니, 체스판의 검은 칸에 위치한 비숍은 검은 칸에만 영향을 주고, 흰 칸에 위치한 비숍은 흰 칸에만 영향을 줄 수 있다는 것을 알게 됐다.

(검은 칸 비숍은 자신이 영향을 줄 수 있는 오른쪽 위 -> 왼쪽 아래 라인도 왼쪽 위 -> 오른쪽 아래 라인도 모두 검은 칸만 있음)

따라서 어차피 서로의 결정에 영향을 주지 않으므로 검은색 칸들을 가지고 있는 라인들만 따로 백트래킹을 하고, 흰색 칸들을 가지고 있는 라인들만 따로 백트래킹을 해도 된다는 것을 깨달았다.

이 경우 시작 복잡도는 $N^N * 2$로 시간 초과 없이 문제를 해결할 수 있게 되었다.

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

public class Main {

    static int N;
    static int[][] map;

    static boolean[] leftToRight;

    static int odd;
    static int even;

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        map = new int[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());
            }
        }

        // 왼쪽 위에서 오른쪽 밑으로 향하는 대각선 방향에는 비숍이 하나만 올 수 있음
        leftToRight = new boolean[N * 2 - 1];

        odd = 0; even = 0;
        back_tracking(0, 0);
        back_tracking(1, 0);
        System.out.println(odd + even);
    }

    // 오른쪽 위에서 왼쪽 아래로 내려오는 대각선 라인에서 하나만 골라 다음 라인 체크
    private static void back_tracking(int d, int count) {

        if(d >= N * 2 - 1) {
            if(d % 2 == 0) even = Math.max(even, count);
            else odd = Math.max(odd, count);
            return;
        }

        int start = d < N ? 0 : d - N + 1;

        for (int i = start; i < N; i++) {
            if(d - i >= 0 && map[i][d - i] == 1 && !leftToRight[getIndex(i, d - i)]) {
                leftToRight[getIndex(i, d - i)] = true;
                back_tracking(d + 2, count + 1);
                leftToRight[getIndex(i, d - i)] = false;
            }
        }
        // 현재 라인에서 아무것도 선택하지 않고 다음 라인으로 넘어감
        back_tracking(d + 2, count);
    }

    private static int getIndex(int x, int y) {

        if(x - y >= 0) return x - y;

        return N * 2 - 1 + x - y;
    }
}