BOJ 1799 비숍

문제 링크 : https://www.acmicpc.net/problem/1799

 

문제 해설

체스판 위에 비숍을 겹치지 않게 놓는 문제입니다.

마음같아선 브루트 포스로 전부 찾아보고 싶지만 시간초과가 나기 때문에 효율적인 방법을 찾아야합니다.

먼저, 비숍을 놓을 수 있는 칸을 흑과 백으로 나눕니다.(비숍은 대각선으로만 움직이기 때문에 서로 다른 색의 칸에는 영향을 못 줍니다.)

비숍을 놓을 수 있는 위치를 흑백으로 나눴다면 백트래킹을 통해 가능한 비숍의 최대 개수를 각각 구합니다.

(대각선은 i + j와 i - j + (N - 1)음수방지 로 2차원 배열이 아닌 1차원 배열로 구현 가능합니다.)

 

코드

import Foundation

if let n = Int(readLine()!) {
    var board = [[Int]]()

    for _ in 0..<n {
        let line = readLine()!.split(separator: " ").map{ Int(String($0))! }
        board.append(line)
    }

    var whiteBoard = [(Int, Int)]()
    var blackBoard = [(Int, Int)]()

    for i in 0..<n {
        for j in 0..<n {
            if board[i][j] == 1 {
                if (i + j) % 2 == 0 {
                    whiteBoard.append((i, j))
                } else {
                    blackBoard.append((i, j))
                }
            }
        }
    }

    // / 대각선
    var leftToRight = [Bool](repeating: false, count: 2 * n)
    // \ 대각선
    var rightToLeft = [Bool](repeating: false, count: 2 * n)


    func dfs(_ arr: [(Int, Int)], _ idx: Int, _ count: Int) -> Int {
        if idx == arr.count {
            return count
        }

        let (x, y) = arr[idx]
        let dir1 = x + y
        let dir2 = x - y + n - 1
		var ret = 0

        if !leftToRight[dir1] && !rightToLeft[dir2] {
            leftToRight[dir1] = true
            rightToLeft[dir2] = true
            ret = max(ret, dfs(arr, idx + 1, count + 1))
            leftToRight[dir1] = false
            rightToLeft[dir2] = false
        }

        ret = max(ret, dfs(arr, idx + 1, count))
        return ret
    }

    let whiteMax = dfs(whiteBoard, 0, 0)
    let blackMax = dfs(blackBoard, 0, 0)
    print(whiteMax + blackMax)
}