[알고리즘] Swift -백준 #9663(N-Queen) -백트래킹

문제링크

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

9663번: N-Queen

 

문제

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

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

입력

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

출력

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

예제 입력 1 복사

8

예제 출력 1 복사

92

 

 

 

 

분석

가로세로 n 크기인 체스판위에 퀸 n개를 서로 공격할 수 없게 놓은 방법을 찾는 문제

체스에서 퀸은 가로 세로 대각선 모든 방향으로 어디든 갈 수 있는 말이다.

n이 주어졌을 때 퀸을 놓는 방법의 수를 구하는 문제다.

 

풀이 과정

퀸은 같은 행, 같은 열에 있는 다른 퀸을 잡을 수 있기에 각 행,열에 하나만 있어야 한다.

첫번째 행에 퀸을 하나두고 두번째 행에 하나두는 식으로 진행한다.

i+1번째 행에서 퀸을 둘 곳이 없다면 i 번째 행으로 돌아와서 다시 다른 곳에 두고 i+1번째 행으로 간다.

i행에서 각 칸마다 퀸을 하나 둔다.

 

 

j열(세로)에 퀸을 둔적이 있는 지 확인한다.

func back(i: Int) {
    if i == n {
        result += 1
        return
    }
    
    for j in 0..<n {
        if !col[j] && !diagonal(y: i, x: j) {
            map[i][j] = true
            col[j] = true
            
            back(i: i+1)
            
            map[i][j] = false
            col[j] = false
        }
    }
}

 

 

(i-1, j) (i-2, j) ... 에 퀸이 있는 지 확인한다.

한 행에 하나의 퀸만 있을 수 있기에 퀸을 놓으면 바로 다음 행으로 넘어간다.

 

대각선 방향에 퀸이 있는 지 확인한다.

func diagonal(y: Int, x: Int) -> Bool {
    for k in 1..<y+1 {
        if 0 <= x-k && map[y-k][x-k] {
            return true
        } else if x+k < n && map[y-k][x+k] {
            return true
        }
    }
    return false
}

 

 

 

 

풀이

let n = Int(readLine()!)!

var map = Array(repeating: Array(repeating: false, count: n), count: n)
var col = Array(repeating: false, count: n)

func diagonal(y: Int, x: Int) -> Bool {
    for k in 1..<y+1 {
        if 0 <= x-k && map[y-k][x-k] {
            return true
        } else if x+k < n && map[y-k][x+k] {
            return true
        }
    }
    return false
}

var result = 0
func back(i: Int) {
    if i == n {
        result += 1
        return
    }
    
    for j in 0..<n {
        if !col[j] && !diagonal(y: i, x: j) {
            map[i][j] = true
            col[j] = true
            
            back(i: i+1)
            
            map[i][j] = false
            col[j] = false
        }
    }
}

back(i: 0)
print(result)

 

결과

 

 

 

---

📂  정리

백트래킹의 대표 유형 문제

문제푸는 방식만 생각하면 코드는 쉽게 풀 수 있다.

퀸의 위치를 두는 방법에 대해서 생각하는데 오래 걸렸다..