[PS] 백트래킹 9663번 N-Queen 답지 참고

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

9663번: N-Queen

처음 풀이

let n = Int(readLine()!)!
var cnt = 0
var graph = Array(repeating: 0, count: n)

func checkQueen(row: Int) -> Bool {
    for i in 0..<row {
        if graph[i] == graph[row] || abs(graph[row]-graph[i]) == abs(row-i) {
            return false
        }
    }
    return true
}


func backtrack(_ depth: Int) {
    if depth == n { // 재귀탈출
        cnt += 1
        return
    }
    
    for i in 0..<n {
        graph[depth] = i
        if checkQueen(row: depth) {
            backtrack(depth+1)
        }
    }
}

backtrack(0)
print(cnt)

 

우선 백트래킹 대표 문제이고, 관련 자료를 참고해서 풀었따.

문제 자체도 이해하는 것도... 참고해서 이해하고.. 

 

이렇게 트리형식으로 그려보면 완전탐색으로 모든 경우를 탐색하는 것보다 조건에 맞지 않는 경우는 가지치고 탐색하는 백트래킹이라는 것을 알 수 있다.

문제는 이걸 어떻게 코드로 쓰냐이다.. 그래서 코드를 참고했다.

우선, 백트래킹을 저번주에 입문문제만 풀어서 응용은 못해서 

- 한정조건과 재귀탈출만 생각했는데 

한정조건 : 무조건 한 행/열에 하나씩, 서로 대각선에 붙어선 안된다.

재귀탈출 : 퀸 개수가 n인 경우 탈출!

 

그리고 NQueen : 무조건 한 행에 하나씩만 놓인다. -> 왜냐하면, 그게 조건임

퀸이 놓인 곳 기준 같은 열과 행 그리고 대각선에는 다른 퀸이 놓이면 안된다는 것이 게임 규칙임...

따라서, 2차원 배열이 아니라 1차원 배열로 만들어도 충분하다. 왜냐면 같은 행이면 안되니까...

 

// 유망성 있는지 검사해주는 함수 -> 한정조건
func checkQueen(row: Int) -> Bool {
    for i in 0..<row {
        if graph[i] == graph[row] || abs(graph[row]-graph[i]) == abs(row-i) {
            return false
        }
    }
    return true
}

 

그리고 그래프를 돌면서 만약 조건에 부합하면 계속해서 백트레킹을 돌고

조건에 부합하지 않으면 조건문을 탈출해서 그 다음 열으로 이동한다.

func backtrack(_ depth: Int) {
    if depth == n { // 재귀탈출
        cnt += 1
        return
    }
    
    for i in 0..<n {
        graph[depth] = i
        if checkQueen(row: depth) {
            backtrack(depth+1)
        }
    }
}

 

근데 이렇게 풀면 시간초과가 나서 안풀린다. 뭔가 파이썬으로 풀면 다른 블로그 보면 맞는 것 같은데.. 흠..

그래서 다른 풀이를 참고했다... 아 어려워..

다른 풀이(https://heecheol.tistory.com/168)를 보면 같은 행과 왼쪽->오른쪽 대각선, 오른쪽->왼쪽 대각선을 고려해서 문제를 풀이했다...

이 방법이 더 어려운 것 같은데.. 훔냐

/*
 NQueen : 무조건 한 행에 하나씩만 놓인다. -> 왜냐하면, 그게 조건임
 퀸이 놓인 곳의 같은 행/열에 놓이면 안되고, 대각선도 안된다.
 그래서 2차원 배열로 만들지 않고, 1차원 배열로 만들어도 된다.
 */

let n = Int(readLine()!)!
var cnt = 0
// 가로줄에 대한 변수
var horizon = Array(repeating: false, count: n)
// 서로 반대 방향의 대각선을 체크하기 위한 변수
// 대각선의 개수는 2n-1개로 동일하다. 각각
// 왼쪽상단에서 오른쪽하단 대각선은 x-y 차가 같다. 대신 대각선의 위치에 따라 값이 달라진다.
// -3, -2, -1, 0, 1, 2, 3으로 달라져서 0~6으로 값을 바꾸려면 n-1을 더해준다.
var leftToRight = Array(repeating: false, count: 2*n-1)
// 오른쪽상단에서 왼쪽하단 대각선은 x+y 합이 같다.
var rightToLeft = Array(repeating: false, count: 2*n-1)

// 한정조건 : 무조건 한 행/열에 하나씩, 서로 대각선에 붙어선 안된다.
// 재귀탈출 : 퀸 개수가 n인 경우 탈출!

// 시작하는 인덱스, 하나씩 증가해서 이전 것은 갖지 않고
// row가 커질수록 그 다음 단계 검사

func backtrack(_ row: Int) {
    if row == n { // 재귀탈출
        cnt += 1
        return
    }
    
    // column을 열이라고 생각 column = 0, row = 0 즉, (0,0)부터 퀸을 두면서 체크 시작
    // 1열의 각 행에 퀸을 넣고 재귀함수를 통해 나머지 퀸의 자리를 확인하는 것
    // backtrack(0) -> horizon[0], rightToLeft[0], leftToRight[3]
    for column in 0..<n {
        if !horizon[column] && !rightToLeft[column+row] && !leftToRight[column-row+(n-1)] {
            horizon[column] = true
            rightToLeft[column+row] = true
            leftToRight[column-row+(n-1)] = true
            backtrack(row+1)
            horizon[column] = false
            rightToLeft[column+row] = false
            leftToRight[column-row+(n-1)] = false
        }
    }
    
}

backtrack(0)
print(cnt)

같은 행에 그리고 각각의 대각선에 true라는 것은 퀸이 있다는 것으로 받아들이면 된다.