[Swift] 백준9663번 N-Queen 문제풀이

대각 공식을 몰라 애먹은 문제.. 남겨두고 다시 풀어보면 좋을 것 같아서 포스팅합니다!

 

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

9663번: N-Queen

백트래킹으로 풀어야 한다는걸 알면서도 대각체크를 어떻게 해줘야할지 몰라 해설을 보고 풀었습니다.

스스로 푼게 아니기에 또 까먹을까봐 블로그 포스팅을 남기고 추후에 제가 보고 쉽게 이해하기 바라며 포스팅합니다!

우선 이 문제를 보고 처음 풀이 접근 방법을 떠올려보자면 많은 사람들이 이렇게 추측하겠죠!

퀸은 가로로 또는 세로로 공격이 가능하니까 행 하나당 하나의 퀸을 놓을 수 있겠다! 또는 열 하나에 하나의 퀸이 있겠다!

맞습니다! 첫 접근은 그렇게 하는게 맞구요! 문제는 대각은 어떻게 체크할까? 이겠죠!

이거는 수학적으로 쉬운 접근 방법이 있어요!

바로 배열에서 좌측대각과 우측 대각의 비밀이죠!

위 그림과 같은 3 x 3 배열이 있다고 칩시다. 좌측 대각선은 어떤 규칙이 보이시나요??

넹 좌측 대각의 x + y는 모두 같아요! 

우측 대각은 y-x와 같습니다.

하지만 코드상에서는 편의를 위해 0부터 시작하기 위해서 +n-1을 취해줬습니다!

위 성질들을 이용해서 백트래킹을 돌면서 

1. 같은 열에 있는지 체크 ( n개의 배열 )

2. 좌측 대각에 놓을 수 있는지 체크 (참고로! 대각은 2*n -1개의 배열의 개수를 가집니다!)

3. 우측 대각에 놓을 수 있는지 체크 (참고로! 대각은 2*n -1개의 배열의 개수를 가집니다!)

하면서 퀸을 놓으면 됩니다!

 

let n = Int(readLine()!)!

var check1 = Array(repeating: false, count: n)
var check2 = Array(repeating: false, count: 2*n-1)
var check3 = Array(repeating: false, count: 2*n-1)

var count = 0

func backTracking(_ curY: Int) {
    if curY == n { // 현재 뽑은 개수가 n과 같으면 종료
        count += 1
        return
    }
    
    for i in 0..<n {
        if check1[i] || check2[i+curY] || check3[curY-i+n-1] { continue }
        // 열|좌측대각|우측대각 방문 표시
        check1[i] = true
        check2[i+curY] = true
        check3[curY-i+n-1] = true
        
        backTracking(curY+1) // 이번 열에서 뽑고 다음 행 뽑으러
        
        // 열|좌측대각|우측대각 방문 표시 지우기 이번 행에선 이번 열을 안뽑는 경우로 분기
        check1[i] = false
        check2[i+curY] = false
        check3[curY-i+n-1] = false
    }
}
backTracking(0)

print(count)