백준 1799 비숍 Kotlin (백트래킹)

문제 출처 : https://www.acmicpc.net/problem/1799

1799번: 비숍

문제

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

< 그림 1 >

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

< 그림 2 >

< 그림 3 >

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

입력

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

출력

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

알고리즘 분류

• 백트래킹

풀이

2021.09.02 - [알고리즘 문제 풀이/백준] - 백준 9663 N-Queen Kotlin,c (백트래킹)

백준 9663 N-Queen Kotlin,c (백트래킹)

위 문제를 먼저 풀고 비숍 문제를 푸는 것을 추천한다.

처음 풀이는, n-queen처럼 2,2칸에 비숍을 놓았을 때, 00, 11, 13, 04 칸을 검사하는 식으로 하였으나,

시간 초과였다.

그래프의 모든 칸이 1로 주어졌을 때,

한 칸당 비숍을 놓을지 안 놓을지(2가지)가 총 n*n칸이므로 O(2^(n*n)) 시간 복잡도가 나오고,

이는 10초의 시간제한을 초과한다.

00	01	02	03	04
10	11	12	13	14
20	21	22	23	24
30	31	32	33	34
40	41	42	43	44

 

결국 다른 분의 블로그를 참고했는데 이분의 글이 가장 이해가 잘 됐다.

https://j2wooooo.tistory.com/80

 

우선 문제의 핵심은 진짜 체스판처럼 흑과 백으로 생각하는 것이다.

00	01	02	03	04
10	11	12	13	14
20	21	22	23	24
30	31	32	33	34
40	41	42	43	44

이처럼 파란색과 노란색으로 구분하는 이유는,

파란색과 노란색에 각각 놓인 두 비숍은 서로에게 영향을 미치지 않기 때문이다.

이렇게 나누면, 노란색에 비숍을 놓는 경우 + 파란색에 비숍을 놓는 경우

O(2^(n/2 * n/2))로 통과할 수 있다.

 

이를 구현하는 것은 다음과 같다.

 

1. 00 시작, 01 시작으로 두 개의 백트래킹을 돌린다(노란색, 파란색)

2-0. 대각선당 하나의 상태(해당 대각선에 비숍이 있는지 없는지)를 가진다. 이를 left[], right[]로 저장한다.

2-1. 위 그래프의 인덱스를 보면 왼쪽 대각선은 r-c의 절댓값이 같고, 오른쪽 대각선은 r+c값이 같다.

2-2. 하지만 절댓값으로 왼쪽 대각선의 상태를 저장하면 20, 31, 42 왼쪽 대각선과, 02,13,24 왼쪽 대각선이 겹친다.

2-3. 따라서 r-c+n으로 왼쪽 대각선의 상태를 겹치지 않게 한다.

3. 위 그래프를 잘 보고 r,c의 인덱스를 잘 다뤄보자.

4. 행이 끝까지 다다르면 color 별로 비숍의 최댓값을 저장하고, color 별 비숍의 최댓값을 더한 값을 출력한다.

 

코드(통과)

import kotlin.math.*
var answer =arrayOf(0,0)
val left = BooleanArray(20)
val right = BooleanArray(19)
fun backTracking( i : Int, j: Int, n : Int,graph : Array<IntArray>, cnt : Int, color : Int){
    var r = i
    var c = j
    if (c >= n) {
        r++;
        if(c%2 == 0) c = 1;
        else c = 0;
    }
    if (r >= n) {
        answer[color] = max(answer[color], cnt);
        return;
    }
    //그래프가 1(비숍을 놓을 수 있는 칸)이고, 해당 칸의 왼쪽 대각, 오른쪽 대각에 비숍이 없다면!
    if(graph[r][c]==1 && !left[c-r+n] && !right[r+c]){
        left[c-r+n]=true
        right[r+c]=true
        backTracking(r,c+2,n,graph,cnt+1,color)
        left[c-r+n]=false
        right[r+c]=false
    }
    backTracking(r,c+2,n,graph,cnt,color)


}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val n = br.readLine().toInt()
    val graph = Array(n){
        br.readLine().split(' ').map { it.toInt() }.toIntArray()
    }
    backTracking(0,0,n,graph,0,0)
    backTracking(0,1,n,graph,0,1)
    write("${answer[0]+answer[1]}")
    close()
}

코드(시간 초과)

import kotlin.math.*
var answer =0

fun check(r : Int, c : Int, n : Int, graph : Array<IntArray>):Boolean{

    for(row in r-1 downTo 0 step 1){
        if(c-(r - row)>=0 && graph[row][c-(r - row)] == 2) return false
        if( c+(r-row)<n && graph[row][c+(r-row)]==2){
            return false
        }
    }
    return true
}

fun backTracking(row : Int , idx : Int, n : Int,graph : Array<IntArray>, cnt : Int){
    var i = idx
    while(i<n*n) {
        val r = i / n
        val c = i % n
        if (graph[r][c] == 1) {
            if (check(r, c, n, graph)) {
                graph[r][c] = 2
                backTracking(r, i+1, n, graph, cnt + 1)
                graph[r][c] = 1
            }
        }
        i++
    }
    answer = max(answer,cnt)
    return
}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val n = br.readLine().toInt()
    val graph = Array(n){
        br.readLine().split(' ').map { it.toInt() }.toIntArray()
    }
    val bishop = IntArray(n)

    backTracking(0,0,n,graph,0)
    write("$answer")
    close()
}