백준 1799번 비숍 - 스위프트(Swift) 풀이 + 그림 설명

 

---

 

1. 백트래킹으로 비숍을 하나씩 놓아본다.
2. 현재 비숍들이 놓인 상태를 대각선 비트 마스킹으로 표시한다.
3. 검은색 칸과 흰색 칸을 따로 생각해서 구한다.

 

1. 백트래킹으로 비숍을 하나씩 놓아본다.

 비숍을 하나씩 놓아본다. 각 칸을 순차적으로 순회하면서 해당 칸에 비숍을 놓는 경우와 놓지 않는 경우를 다 해보면 된다. 다음칸으로 넘어갈 때는 비숍의 경로가 겹치면 안 되기 때문에 현재 체스판의 상황을 같이 넘겨주어야 한다.

 

2. 현재 비숍들이 놓인 상태를 대각선 비트 마스킹으로 표시한다.

 현재 체스판 상태를 N*N짜리 배열로 넘겨주는 것은 비효율적이다. 어차피 비숍은 대각선으로만 이동할 수 있으므로, 대각선마다 비숍이 위치하는지 여부만 넘겨주자. 현재 칸이 속한 두 종류의 대각선을 모두 확인해서, 두 대각선에 아무것도 없으면 현재 칸에 비숍을 놓아볼 수 있다.

 대각선은 아래와 같이 두 종류가 있다. 2시-8시 방향과 4시-10시 방향. 아래 코드에서는 각각을 right, left로 칭했다.

 각 대각선에 번호를 매긴 뒤, i번 대각선에 비숍이 위치한다면 i번 비트를 켜주는 비트 마스킹 방식을 사용하였다. 번호는 아래와 같은 방식으로 매겼다.

 

3. 검은색 칸과 흰색 칸을 따로 생각해서 구한다.

 비숍은 대각선으로만 이동이 가능하다. 따라서 체크무늬로 색칠된 체스판에서 검은색 칸에 위치한 비숍은 절대 흰색 칸으로 이동할 수 없다. 반대도 마찬가지이다. 따라서 검은색 칸에 놓을 수 있는 비숍의 최대 개수 + 흰색 칸에 놓을 수 있는 최대 개수를 따로 구해서 더해주면 시간을 줄일 수 있다.

반응형

---

import Foundation

var N = 0
var board = Array(repeating: [Int](), count: 10)

func findDiagonal(row: Int, col: Int) -> (left: Int, right: Int) {
    let left = (row + col) / 2
    let right = (row + (N - 1 - col)) / 2
    
    return (left, right)
}

func check(row: Int, col: Int, leftDiagonal: Int, rightDiagonal: Int) -> Bool {
    let diagonals = findDiagonal(row: row, col: col)
    let checkLeft = leftDiagonal & (1 << diagonals.left) == 0
    let checkRight = rightDiagonal & (1 << diagonals.right) == 0
    let checkBoard = board[row][col] == 1
    
    return checkLeft && checkRight && checkBoard
}

func next(row: Int, col: Int) -> (row: Int, col: Int) { // 다음 검은/흰 칸 반환
    var nextRow = row
    var nextCol = col + 2
    
    if nextCol >= N {
        nextCol += 1
        nextCol %= 2
        nextRow += 1
    }
    
    return (nextRow, nextCol)
}

func bishop(row: Int, col: Int, leftDiagonal: Int, rightDiagonal: Int) -> Int {
    if row >= N { return 0 }
    
    var ret = 0
    let next = next(row: row, col: col)
    
    // 1. (row, col)에 놓지 않는 경우
    let skip = bishop(row: next.row,
                  col: next.col,
                  leftDiagonal: leftDiagonal,
                  rightDiagonal: rightDiagonal)
    ret = max(ret, skip)
    
    // 2. (row, col)에 놓는 경우
    if check(row: row, col: col, leftDiagonal: leftDiagonal, rightDiagonal: rightDiagonal) {
        let diagonals = findDiagonal(row: row, col: col)
        let put = 1 + bishop(row: next.row,
                         col: next.col,
                         leftDiagonal: leftDiagonal | (1 << diagonals.left),
                         rightDiagonal: rightDiagonal | (1 << diagonals.right))
        ret = max(ret, put)
    }
    
    return ret
}

func solution() {
    N = Int(readLine()!)!
    
    for i in 0..<N {
        board[i] = readLine()!.split(separator: " ").map{ Int(String($0))! }
    }
    
    let black = bishop(row: 0, col: 0, leftDiagonal: 0, rightDiagonal: 0)   // 체스판의 검은 칸
    let white = bishop(row: 0, col: 1, leftDiagonal: 0, rightDiagonal: 0)   // 체스판의 흰 칸
    let result = black + white
    
    print(result)
}

solution()