[swift 알고리즘] 백준_9663 N-Queen

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

 

 

해결방법 

퀸은 한 열에 한 개만 존재 가능하다. 여기서 아이디어를 착안하여, 한 열에 퀸을 배치하고 dfs알고리즘을 돌린다고 생각했습니다. 문제가 되는 것은 퀸을 배치할 수 있는지 없는지 이다. 퀸이 과연 위치시킬수 있는지는 대각선에 관련한 지식을 사용했습니다. (비숍문제에 설명되어 있습니다.) 좌표평면에 대각선이 겹치는지 확인 하는 것을 다음과 같은 식으로 해결 가능했습니다.

 

 

따라서 수직 방향과, 왼쪽 대각선, 오른쪽 대각선의 관한 배열을 만들고 이 위치에 Queen을 배치시킬 수 있는지에 대한 여부를 확인하였습니다. 그리고 만약 배치시킬 수 있다면 다음 열에도 배치시키도록 코드를 만들었습니다.

 

 

해결코드

 

func sol() {
  let N = Int(readLine()!)!
  var vs = Array(repeating: true, count: N)
  var lds = Array(repeating: true, count: N * 2)
  var rds = Array(repeating: true, count: N * 2)

  var res: Int = 0
  func next(_ row: Int, _ depth: Int) {
    if depth == N {
      res += 1
      return
    }
    
  for col in 0..<N {
    if vs[col] && lds[row + col] && rds[row - col + N - 1] {
        vs[col] = false
        lds[row + col] = false
        rds[row - col + N - 1] = false
        next(row + 1, depth + 1)
        vs[col] = true
        lds[row + col] = true
        rds[row - col + N - 1] = true
      }
    }
  }
  next(0, 0)
  print(res)
}