Algorithm) Programmers-N-Queen swift

https://school.programmers.co.kr/learn/courses/30/lessons/12952#

프로그래머스

백트래킹으로 유명한 문제죠 예~전에 백준사이트에서 c++로 풀었던 기억이 있어서 어렵지 않게 풀어봤습니다

문제에서 세로로 이동할 수 있으므로 column마다 최대 1개의 비숍을 놓을 수 있기 때문에 2차원 배열이 아닌 1차원 배열을 사용했습니다

col, down_diagonal,up_diagonal 이렇게 세가지 배열을 사용했는데요

col은 말그대로 열 

/  이 방향이 up_diagonal

\ 이 방향이 down_diagonal

col 처럼 대각선도 대각선마다 최대 하나의 비숍을 놓을 수 있으니까요

어 그럼 가로는? 하고 생각하실 수 있는데 대각선을 이용하면 가로는 따로 체크하지 않아도 같이 체크된답니다

(0,1), (1,0) 을 잇는 대각선이 up_diagonal[1]

(0,2), (1,1), (2,0)을 잇는 대각선이 up_diagonal[2]

 

(0,2), (1,3)을 잇는 대각선이 down_diagonal[1]

(0,1), (1,2), (2,3) 을 잇는 대각선이 down_diagonal[2]

이렇게 되는거죠

 

코드 상에서 i가 y, k가 x역할을 한다고 생각하고 코드를 보시면 편할겁니다

import Foundation


var col = [Bool](repeating:false, count: 13)
var down_diagonal = [Bool](repeating:false, count: 25) // 우하향
var up_diagonal = [Bool](repeating:false, count: 25) // 우상향

var ans = 0

func check (_ k: Int, _ n: Int) {
    if k == n {
        ans += 1
        return
    }
    for i in 0..<n {
        if !col[i] && !right_diagonal[k-i+n-1] && !left_diagonal[i+k] {
            col[i] = true
            right_diagonal[k-i+n-1] = true
            left_diagonal[i+k] = true
            check(k+1, n)
            col[i] = false
            right_diagonal[k-i+n-1] = false
            left_diagonal[i+k] = false
            
        }
    }
}

func solution(_ n:Int) -> Int {
    check(0, n)
    return ans
}