[BOJ] 백준 9963 N-Queen (Swift)

문제

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

9663번: N-Queen

풀이

이 문제는 백트래킹 알고리즘을 사용하여 풀이할 수 있습니다.
모든 경우의 수를 확인하면 시간 복잡도는 $O(n^n)$ 일 것이고,
n이 최대 15이므로 437,893,890,380,859,375 번 연산을 하겠네요.. ㄷㄷ

그래서 백트래킹을 사용하여 안되는 경우를 가지치기 해주어야합니다.

n * n 체스판을 떠올리면 2차원 배열을 떠올리기 마련인데,
1차원 배열만 사용해도 무방합니다.

1차원 배열의 index를 열로, 요소를 행으로 생각할 수 있습니다.
예를들어 [1, 0, 2] 라는 Array가 있다면 (0, 1) (1, 0), (2, 2)에 있다고 생각할 수 있습니다.

왜 그럴까요?

체스에서 퀸을 서로 공격할 수 없게 놓으려면, 같은 행과 열에 존재할 수 없습니다.
그래서 열당 하나의 퀸을 놓기 때문에 1차원 Array를 사용할 수 있습니다.

그렇다면 Array에 같은 요소가 있어서도 안되겠네요.
왜냐하면 같은 요소라면 같은 행에 있다는 것과 동일하기 때문입니다.

그리고 대각선도 확인해주어야 합니다.

퀸을 놓을 때, 여태까지 놓은 퀸들의 대각선에 놓지 않아야 합니다.

대각선은 다른 퀸과 행의 차이의 절대값과 열의 차이의 절대값이 같다면 대각선에 놓인 경우입니다.

(3, 3)의 대각선은 (1, 1), (2, 2), (2, 4), (1, 5) 등이 있겠네요
(1, 5)와 (3, 3)을 비교해봅시다.
|(1 - 3)| = 2, |(5 - 3)| = 2 이므로 대각선에 위치한다는 것을 확인할 수 있습니다.

재귀함수를 사용해 퀸을 n개만큼 놓을 수 있다면, 경우의 수를 하나 증가시켜줍시다.
그리고 서로 공격하지 않게 퀸을 놓을 수 있다면, 다음 퀸을 놓아주면 됩니다.

소스코드

후기

시간초과를 많이 겪었던 문제였습니다.
2차원 배열을 사용하지 않고 1차원 배열을 사용한다는 점이 신선했고, 어려웠던 문제였습니다.
다른분들의 풀이를 많이 참고하여 이해했던 문제입니다.