[Swift] 프로그래머스 N-Queen

Problem

 

코딩테스트 연습 - N-Queen

---

Solution

 

해당 문제는 백트래킹(DFS)으로 풀어야 하는 문제입니다.

 

1. 각 행마다 퀸을 놓을 수 있는 위치를 체크한다.

 

각 행마다 퀸은 하나씩밖에 못놓으므로 현재 행의 열들에 공격할 수 있는 퀸이 있는지 체크합니다.

 

만약 공격할 수 있는 퀸이 없다면 현재 위치를 history(퀸의 위치를 저장하는 2차원 배열)에 저장해놓고 다음 행으로 진행합니다.

 

이렇게 진행하면서 가장 마지막 행까지 도달한 경우는 배치할 수 있는 경우이므로 answer(배치할 수 있는 경우 수)를 +1 증가시켜줍니다.

 

func findEnableArrange(n:Int,depth:Int,history:[[Bool]],answer:inout Int) {
    //가장 마지막까지 왔을 경우
    if depth == n {
        //배치 가능한 것이므로 +1 해줌
        answer += 1
        return
    }
    //현재 행에 퀸을 놓을 수 있는지 확인
    for x in 0..<n {
        //공격하지 못한다면
        if isUnableAttack(history: history, x: x, y:depth) {
            var newHistory = history
            newHistory[depth][x] = false
            //dfs로 진행
            findEnableArrange(n: n, depth: depth+1,history: newHistory,answer: &answer)
        }
    }
}

 

2. 공격할 수 있는 퀸이 있는지 체크한다.

 

공격할 수 있는 퀸은 세로방향 그리고 대각선 방향에 퀸이 있는지만 체크하면 됩니다.

 

세로방향은 현재 x의 모든 행을 검사하면 되고

 

대각선일 경우엔 왼쪽과 오른쪽으로 나눠서 퀸이 있는지 확인하면 됩니다.

 

만약 (x,y)의 모든 대각선 방향을 구할 때 규칙은 왼쪽 방향일 경우 (x-abs(y-i),i)를 체크하면 되고 

 

오른쪽을 검사할 경우 (x+abs(y-i),i)를 체크하면 됩니다.

 

//공격이 불가능한지 체크한다
func isUnableAttack(history:[[Bool]],x:Int,y:Int) -> Bool {
    for i in 0..<history.count {
        //세로 확인
        if !history[i][x]  {
            return false
        //대각선으로 왼쪽 확인
        }else if 0..<history.count ~= x-abs(y-i) && !history[i][x-abs(y-i)] {
            return false
        //대각선으로 오른쪽 확인
        }else if 0..<history.count ~= x+abs(y-i) && !history[i][x+abs(y-i)] {
            return false
        }
    }
    return true
}

 

예를 들어 현재 위치가 2,2라면 x =2 이고 y=2 입니다.

 

왼쪽 방향의 대각선을 0부터 n-1까지 검사한다면 0번째행은  (2 - abs(2-0),0) = (0,0)을 체크해줍니다.

 

 

 

 

오른쪽도 마찬가지로 0번째 행을 검사한다면 (2 + abs(2-0),0) = (4,0)을 체크해주면 됩니다.

 

 

3. 배치 가능한 경우 수를 반환해줍니다.

 

return answer

---

Source Code

 

---

P.S

 

백트래킹 문제라고 해서 좀 겁먹었는데 그냥 백트래킹이 DFS구나 라는 것을 알게 되었다.

 

또 퀸의 위치를 그냥 같은 행에서 x번째들만 검사하면 됐는데 바보같이 모든 행과 모든 열을 검사하게 구현해서

 

시간초과가 났었다...

---

다른 사람 풀이 중 좋다고 생각하는 풀이

 

아래와 같이 대각선을 체크할 때 abs(x-i) - abs(y-chess[i])로 체크하면 훨씬 간단하게 구할 수 있었다.

 

func solution(_ n:Int) -> Int {
    var chess = [Int].init(repeating: -1, count: n)
    var answer = 0

    func check(_ x: Int, _ y: Int) -> Bool {
        for i in 0..<x {
            if chess[i] == y || abs(x - i) - abs(y - chess[i]) == 0 { return false }
        }

        return true
    }

    func dfs(_ cnt: Int) {
        if cnt == n {
            answer += 1
            return
        }

        for i in 0..<n {
            if check(cnt, i) {
                chess[cnt] = i
                dfs(cnt + 1)
                chess[cnt] = -1
            }
        }
    }

    dfs(0)

    return answer
}