[Algorithm]Programmers_12952_N-Queen_Go

문제 링크

N-Queen : 링크

문제 풀이

Well Known 이군요..

1. 체스에서 퀸의 움직임을 알아둔다. 가로 세로 대각선 완전 만능
2. row, col, diagnol 방향 모두 가능하다면 하나씩 체크하면서 넘어간다.
3. 끝까지 도착했다면 모든 조건에 만족했다는 뜻! answer += 1

package q12952

var board [][]bool
var colCheck []bool

func initBoard(n int) {
    board = make([][]bool, n)
    colCheck = make([]bool, n)
    for i := 0; i < len(board); i++ {
        board[i] = make([]bool, n)
    }

}

var answer int

func goBackTracking(size, row int) {
    if row == size {
        answer++
        return
    }
    for i := 0; i < size; i++ {
        if !colCheck[i] && checkBoard(size, row, i) {
            board[row][i] = true
            colCheck[i] = true
            goBackTracking(size, row+1)
            colCheck[i] = false
            board[row][i] = false
        }
    }
}

func checkBoard(size, row, col int) bool {
    if !diagnolRightDown(size, row, col) {
        return false

    }
    if !diagnolLeftDown(size, row, col) {
        return false
    }
    return true
}

func diagnolRightDown(size, row, col int) bool {
    for row >= 0 && col >= 0 {
        if board[row][col] {
            return false
        }
        row--
        col--
    }

    return true
}
func diagnolLeftDown(size, row, col int) bool {
    for row >= 0 && col < size {

        if board[row][col] {
            return false
        }
        row--
        col++
    }
    return true
}

func solution(n int) int {
    initBoard(n)
    goBackTracking(n, 0)
    return answer
}