[Swift] 백준_N-Queen(9663)

문제

 

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

9663번: N-Queen

 

 

풀이

 

너무 어려웠다. 구현하는게 어렵다기보단 아이디어를 생각해내는게 안돼서 참고했따ㅠ

 

퀸은 8방향 전부 움직일 수 있다. 하나의 퀸이 들어오면 세로줄, 가로줄, 왼쪽 대각선, 오른쪽 대각선을 각각 확인하면된다. 

이 범위 안에 있지만 않으면 방금 들어온 퀸과 서로 공격할 수 없는 것이다. 

 

정리하면 각 행 또는 열에는 반드시 하나의 퀸만 존재해야하고, 양쪽 대각선에 퀸이 없어야한다.

 

 

코드에 대해서 설명해보자면,

우선 세 개의 변수가 필요했다. solution함수 내의 반복문에서 i를 열이라고 생각했기때문에 가로줄이 사용중인지를 나타내는 변수와 두 개의 대각선을 나타내는 변수를 선언했다.

 

4x4체스판을 생각해보면 가로줄은 4줄이 있기 때문에 count를 n으로 초기화를 해주었다.

 

다음으로 오른쪽위에서 왼쪽 아래로 긋는 대각선을 생각하면 총 7개의 대각선이 그려진다. 대각선은 (0,0)에 하나, (0,1)과 (1,0)을 포함하는 대각선 하나, (0,2), (1,1), 그리고 (2,0)을 포함하는 대각선 등이 있다. 각 대각선을 이루는 점들을 보면 x + y의 값이 전부 같다. rightToLeft [x + y]의 값이 true라면 이미 해당 대각선에 퀸이 있다는 것을 의미한다. 

 

마찬가지로 반대쪽 대각선을 확인해보면 개수는 2n - 1로 같지만 x와 y의 관계가 다르다. (0,3), (0,2)와 (1,3) 의 관계를 확인해보면 이번엔 합이 아니라 차가 같다는 것을 알 수 있다. 다만 계속하다보면 값이 3, 2, 1, 0, -1, -2, -3이 되므로 배열로 확인하기 위해서는 0부터 6의 값을 갖기위해 n - 1을 더해주어야한다.

 

 

예시를 확인해보겠따.

 

solution(0)이 실행되면 가장 처음 (0,0)칸에 퀸이 찰 것이고, 첫 번째 가로줄과 두 개의 대각선이 사용되었기 때문에 horizon[0], rightToLeft[0], leftToRight[6]이 true로 바뀐다.

이후에 바로 solution(1)이 실행되면 반복문은 0부터 n까지 count값을 1로 갖고 돌게된다. 

horizon[0]이 차있으므로 다음으로 넘어가면 i는 1이된다. i가 1이고 count가 1인 경우에는 leftToRight[6]이 true인 상태라서 넘어간다. 다음으로 i는 2인 경우에는 퀸이 들어올 수 있으므로 solution(2)가 실행된다. 

 

헷갈릴 수 있지만 간단히 생각하면 1열의 각 행에 퀸을 넣고 재귀함수를 통해 나머지 퀸의 자리를 확인하는 것이다. i를 행, count를 열로 생각하면 된다.

다시 말해서, 1열에 퀸이 놓이면 count가 1이 증가하므로 2열에서 조건을 만족하는 자리가 있는지 확인하는 것이다.

import Foundation

let n = Int(readLine()!)!
var result = 0
var horizon = Array(repeating: false, count: n)
var leftToRight = Array(repeating: false, count: 2 * n - 1)
var rightToLeft = Array(repeating: false, count: 2 * n - 1)

func solution(_ count: Int) {
    if count == n {
        result += 1
        return
    }
    for i in 0..<n {
        if !horizon[i] && !rightToLeft[i + count] && !leftToRight[i - count + (n - 1)] {
            horizon[i] = true
            rightToLeft[i + count] = true
            leftToRight[i - count + (n - 1)] = true
            solution(count + 1)
            horizon[i] = false
            rightToLeft[i + count] = false
            leftToRight[i - count + (n - 1)] = false
        }
    }
}
solution(0)
print(result)

 

 

_____________________________________________________________________________________________________

 

 

문제를 많이 풀자. 아이디어가 잘 안떠오른다.