1.
문제 설명
: N * N개의 배열에 N개의 퀸을 서로 공격할 수 없게 놓는 문제
: 백트래킹의 대표격인 알고리즘이다.
2.
접근
: 문제에서 주어진 N의 범위가, 1 ≤ N < 15였기 때문에, 1 * 1 배열부터 직접 배치해보았다.
: 4 * 4, 5 * 5를 배치하던 도중, 1차원 배열로 해석할 수 있지 않을까?라는 생각이 들었고, 배열의 인덱스를 행, 배열의 값을 열로 두었다.
: 이렇게 했을 때, 다음 단계는 각 배열의 인덱스, 값들 간의 관계를 설정하는 것인데, Queen의 이동범위에 따라 제한해주는 과정이 필요했다. 각 행마다 한 개씩 둘 것이므로 가로는 생각하지 않아도 되었고 세로, 대각선에 대한 제한사항이 필요했다.
: 대각선의 경우, arr[index] = value라는 값이 있을 때, index - 1까지의 값들을 생각해주면 되었다. 위에서 아래로 차근차근 Queen을 하나씩 배치해나가기 때문으로 x, y(index, value)라는 값이 있을 때, 해당 값의 대각선에 위치한다는 것은 x - n, y - n이거나 x - n, y + n로 생각할 수 있고, n은 0부터 index - 1의 값이다.
⇒ 이를 구현하기 위한 방법을 대충 작성해 문제를 풀고, 다른 분의 풀이를 보았는데, 절댓값을 기가 막히게 사용해서 인상적이었다.
⇒ 행과 열의 관계를 이용해서 접근했는데, , 로 index, value 기준으로 좌측 대각선에 위치할 때, 차가 서로 같다. 우측 대각선의 경우, 절댓값이 같다.
⇒ , , -n, n으로 두 값에 절댓값을 사용하면 우측 대각선의 경우, 차의 절댓값이 같은 경우로 한정할 수 있다.
: 같은 열의 경우, value 값이 중복되는 경우로 체크해주었다.
: 이제 이것들을 재귀를 통해 구현해주면 되었는데, 단순히 위 조건들을 체크해주는 함수를 하나 만들어서, 0부터 N까지 수행하도록 처리하도록 해주기만 하면 되었다.
