규칙 찾기

• Queen은 상하좌우 및 모든 방향의 직선 대각선을 이동할 수 있다.

1. 상, 하 | 좌, 우

• 매우 쉽게 찾을 수 있는 규칙으로 Queen이 특정 위치에 존재할 때 같은 행, 같은 열에는 Queen이 존재할 수 없다.

2. Positive Diagonal

• 대각선으로 이동할 수 있을 때 좌상, 우하 방향으로 이동하는 것을 Positive 방향이라고 가정하자.
• 각 행, 열에 대해 다음과 같은 규칙을 찾을 수 있다.

• 만약 우하 방향으로 이동한다면, 열은 +1 | 행은 +1 되기에(좌상 방향도 부호는 바뀌지만 마찬가지) 뺄셈은 항상 같을 수밖에 없다.
• 따라서 (행 - 열) 사칙연산을 수행하면 이동 가능한 모든 Positive 대각선에서 모두 같은 값이 나온다.

3. Negative Diagonal

• 대각선으로 이동할 수 있을 때 좌하, 우상 방향으로 이동하는 것을 Negative 방향이라고 가정하자.
• 마찬가지로 다음과 같은 규칙을 찾을 수 있다.

• 우상 방향으로 이동한다면, 열은 + 1 | 행은 -1 되기에 둘의 덧셈은 항상 같을 수밖에 없다.
• 따라서, (행 + 열)의 값은 Negative 방향의 대각선의 이동 경로에서 모두 같다.

문제 풀이

위 3가지 규칙을 사용해서 문제를 풀 수 있다.

1. 우선 같은 행에는 Queen이 존재할 수 없으므로 행은 검사하지 않고 Queen을 놓는 순간 다음 행으로 넘어가는 방식으로 계산하면 연산을 줄일 수 있다.
2. 첫 번째 행에 대해서만 Queen을 하나씩 배치해 보고 나올 수 있는 모든 상황의 갯수가 정답이다. 첫 번째 행에 모두 배치한 이후 다음 행으로 넘어가면 중복되는 결과가 나온다.

for (let i = 0; i < n; i++) {
	// 각 index마다 Q을 배치했다고 가정하고 연산 후 넘어간다.
	// 이는 첫 번째 행에 대한 배치이다.
}

3. 확인해야 될 조건은 3가지(상하 | Positive | negative)이므로 각각을 Set 객체를 통해 값을 저장해놓고, Set.prototype.has() 메서드를 통해 Queen을 놓을 수 있는지 없는지 검사한다.

for (let i = 0; i < n; i++) {
  const col = new Set();
  const pos = new Set();
  const neg = new Set();

  col.add(i);
  pos.add(0 - i);
  neg.add(0 + i);
}

4. 첫 번째 행이 아닌 두 번째 행부터 Queen을 배치할 때 가능한 상황이 다음과 같이 두 개 이상일 수 있다. 따라서, 반복문이 아닌 DFS를 이용해서 Brute Force 방식으로 순회하도록 작성했다.

const dfs = (r, n, col, pos, neg) => {
    if (r === n) {
			// 모든 행을 검사했을 때 처리
    } else {
			// DFS의 파라미터로 행(r)을 전달해주고, 열(c)은 for 문으로 순회하면서 확인한다.
      for (let c = 0; c < n; c++) {

				// 만약 상하, pos, neg 방향에 Queen이 존재하면 다음 열로 넘어간다.
        if (col.has(c) || pos.has(r - c) || neg.has(r + c)) {
          continue;
        }
				
				// 겹치지 않으면 해당 위치에서의 상하, pos, neg 포지션을 Set 객체에 추가하고,
				// 다음 행으로 넘어간다.(재귀 호출한다.)
        col.add(c);
        pos.add(r - c);
        neg.add(r + c);
        dfs(r + 1, n, col, pos, neg);

				// DFS를 재귀 호출한 후 다음 행을 확인하기 위해 다시 delete 해준다.
        col.delete(c);
        pos.delete(r - c);
        neg.delete(r + c);
      }
    }
  };

작성 완료된 코드

const solution = (n) => {
  let answer = 0;

  const dfs = (r, n, col, pos, neg) => {
    if (r === n) {
      answer += 1;
    } else {
      for (let c = 0; c < n; c++) {
        if (col.has(c) || pos.has(r - c) || neg.has(r + c)) {
          continue;
        }

        col.add(c);
        pos.add(r - c);
        neg.add(r + c);
        dfs(r + 1, n, col, pos, neg);
        col.delete(c);
        pos.delete(r - c);
        neg.delete(r + c);
      }
    }
  };

  for (let i = 0; i < n; i++) {
    const col = new Set();
    const pos = new Set();
    const neg = new Set();
    col.add(i);
    pos.add(0 - i);
    neg.add(0 + i);

    dfs(1, n, col, pos, neg);
  }

  return answer;
};