[Swift 알고리즘] 프로그래머스 - N Queen

안녕하세요 코코종입니다.

오늘은 백준대신 프로그래머스로 돌아왔습니다 크크...

ㅇ.ㅣ게 왜 레벨 2ㅇㅑ...

import Foundation

func solution(_ n: Int) -> Int {
    let board: [Int] = Array(repeating: -1, count: n) // 한 행에는 하나만 가능하니까 어디에 놓였는지 체크용
    var answer: Int = 0
    
    dfs(board: board, depth: 0, n: n, answer: &answer)
    
    return answer
}

func dfs(board: [Int], depth: Int, n: Int, answer: inout Int) {
    if depth == n {
        answer += 1
        return
    }
    
    for i in 0..<n {
        if isValid(r: depth, c: i, board: board) {
            var bboard = board // 사본
            bboard[depth] = i // depth 행의 값은 i
            dfs(board: bboard, depth: depth + 1, n: n, answer: &answer)
        }
        
        
    }
}

func isValid(r: Int, c: Int, board: [Int]) -> Bool {
    for i in 0..<r {
        if board[i] == c { // 같은 열에 이미 배치
            return false
        }
        
        if abs(r - i) == abs(c - board[i]) { // 대각선 - 행의 차이, 열의 차이의 절댓값이 같으면
            return false
        }
    }
    
    return true
    
}

이번 문제는 dfs지만 완탐이 아닌 백트래킹으로 아예 가망이 없는 친구들은 안지나가는 방식입니다.

이문제는 대학교때 컴공 수업을 하나 들었는데 교수님이 노가다 과제 vs 이 문제 풀어서 제출해오기를 하셨는데.... 네... 구글에 검색해보면 되는데 아무리 생각해도 코드로 짤수가 없어서..... 그냥 노가다 과제를 했다는 전설이.....하하....

 

처음에는 당연히 n*n으로 배열을 만들어서 푼다고 생각했었는데요. 이 문제를 어디서 본 적이 있다보니... 대충의 아이디어는 알고 시작했습니다.(이차원으로 하면 시간초과가 난다고 하네요 참내... 이게 왜 2렙) 헷갈리는 것 중에 하나는 board[i]가 그 행에 i번째 열에 퀸을 뒀다! 이건데요. 이차원을 일차원으로 생각하다보니까 머리가 빙빙~~ 돌았습니다.

 

쉽게 설명하면 0..<n 으로 행을 내려오면서 그 행에는 다른 퀸을 둘 수 없으니 일차원 배열로 board를 구성하고, 이를 기반으로 내려가면서 혹시나 같은 열이나 대각선에 배치가 되어있나 판단하는 것이었답니다. isValid의 내용중 abs(r-i) == abs(c-board[i]) 를 작성할때는 헷갈려서 종이에 적어가면서 했네요. 그리고 bboard를 만든 이유는 이전에 board를 var로 복사해서 그대로 작성해버리면 백트래킹으로 돌아갈 수가 없이 board가 엉망진창이 되어버리기 때문입니다! (이건 탐색 문제를 여러개 푸시다보면 알겁니다)