Backtracking 백트래킹 대표 문제 ) NQueen - Swift로 구현

NQueen 문제를 푸는데 Swift 풀이가 많이 없어서 올려봅니다.

 

---

Backtracking 이란?

🔥 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다.
→ 즉, DFS를 사용하여 만약 조건에 맞지 않으면 그 즉시 중단하고 이전으로 돌아가 다시 확인하는 것을 반복하면서 원하는 조건을 찾는 알고리즘 입니다.
 
정리하자면,  백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것
🔥 주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현할 수 있습니다.
 

---

N-Queen 문제

NxN 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제

- N-Queen 문제는 N의 크기가 작다면 DFS 방식으로 모든 경우의 수를 탐색하면 답을 찾을 수 있다. 하지만 N의 크기가 커질 수록 탐색해야할 경우의 수가 기하급수적으로 증가하게 됩니다.

 

N-Queen 문제의 풀이 아이디어는 아래 블로그를 참고했어요 ! 완전 설명 굿. !! 이것보다 잘 할 자신이 없어서 넘깁니다. ㅋㅋ

[알고리즘] 백트래킹(Backtracking) | C언어 N-Queen구현

 

저는 위의 글로 이론을 이해한 다음에 다른 언어 풀이를 참고했습니다 !

가장 이해가 잘되는 풀이를 골라서 Swift로 구현해줬습니다 !! 

[백준 / BOJ] - 9663번 N-Queen C++ 풀이

 

위 블로그의 풀이를 참고해서 프로그래머스의 N-Queen 문제를 Swift로 풀었습니당.

func solution(_ n:Int) -> Int {
    
    var chess = Array(repeating: -1, count: n)
    var answer = 0 
    
    // 유망성 검사
    func checkArrangeQueen(row: Int) -> Bool {
        for i in 0..<row {
            if chess[i] == chess[row] || abs(chess[row] - chess[i]) == abs(row - i) {
                // 같은 열이거나 대각선일 경우  
                return false
            }
        }
        
        return true
    }
    
    // 행을 기준으로 DFS. 1행 -> 2행 -> 3행 ...
    
    func dfs(row: Int) {
        
        // 만약에 끝까지 다 배치했을 경우. +1
        if row == n {
            answer += 1
            return
        }
        
        // 하나의 행에서 모든 열의 유망성을 검사한다. 
        for i in 0..<n {
            chess[row] = i // 그 자리에 일단 배치 
            
            if checkArrangeQueen(row: row) {
                // 배치할 수 있다면, 
                dfs(row: row + 1) // 다음 행 DFS
            }
            // 배치할 수 없다면 다음 index로 넘어감.
        }
    }
    
    dfs(row: 0)
    
    return answer
}

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스