프로그래머스, N-Queen

문제

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.
이 배열에는 다음과 같은 속성이 있다.

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

예제

예제 1

	♛
			♛
♛
		♛

		♛
♛
			♛
	♛

Input 	: n = 4
Outpu	: 2

초기값

function solution(n) {
  let answer = 0;
  return answer;
}

---

나의 풀이

알고리즘이 너무나 빈약한 나는 풀지 못했다. 😂
어떻게 풀어야 할지는 머리속에서 구상은 되었으나 이를 표현하지 못하였다. 사실... 알고리즘을 몰른다고 해도 무방하다.
탐색 알고리즘을 이용한다는것을 알게 되었고 이 문제의 경우 깊이 우선 탐색 알고리즘(DFS, Depth First Search)를 사용한다고 한다.

• 퀸은 가로, 세로, 대각선을 n범위를 이동할 수 있다.
• 퀸의 이동 범위에 다른 퀸은 있을 수 없다.
• 2차원 배열로 체스판을 생각하였다.
• 한 행씩 해당 열 위치에 퀸을 놓을 수 있는지 없는지 확인해야한다.
• 퀸의 이동 범위에 다른 퀸의 이동 범위가 겹치지 않게 확인해야한다.
• 각 행에는 하나의 퀸만 있을 수 있다. (가로)
• 각 열에는 하나의 퀸만 있을 수 있다. (세로)
• 하나의 퀸의 위치와 놓을 퀸의 위치의 위치값(x,y)이 일치 하면 안된다. (가로, 세로)
• 하나의 퀸의 위치와 놓을 퀸의 위치는 서로의 위치값의 서로의 x축 위치값의 차이와 y축 위치값의 차이를 나누었을 때 절대값이 1이 되지 않아야 한다. (대각선)
  해당 풀이법은 돌출하지 못하였다...😭

다른 사람의 풀이

다른사람의 풀이도 궁금하여서 찾아보았다.
해당 자료는 baffinlee사이트에서 찾아보았다.

function solution(n) {
	// n의 값이 1이거나, 4 이상이거나, 12 이하여야 한다.
	// n이 2, 3이 될 경우 해답은 나오지 않는다.
	// 제한사항에서 n은 12이하의 자연수라고 한다.
	// 재귀 함수를 사용하여 queen을 놓을 수 있는 수를 찾는다.
	if (n === 1 || n >= 4 || n <= 12) return queen([], n, 0);
	return 0;
}
function queen(points, n, index) {
	let res = 0; // 퀸을 놓을 수 있는 방법의 수
	if (points.length === n) return 1; // 재귀함수를 통해서 반복되다 points의 길이값과 n의 값이 같을 때 놓을 수 있는 방법은 한번 뿐이다.
	for (let i = index; i < n; i++) {
		// 행을 찾을 반복문
		if (points.length !== i) return res; // 현재 행에 퀸이 있는지 없는지 판단한다.
		for (let j = 0; j < n; j++) {
			// 열을 찾을 반복문
			if (!isValid(points, [i, j])) continue; // 현재 열에서 퀸을 놓을 수 있는지 없는지 판단하는 isValid 함수를 사용한다.
			points.push([i, j]); // 일단 현재의 위치에 퀸을 놓는다.
			res += queen(points, n, i + 1); // 재귀함수를 통해 다음의 수와 비교를 한다.
			points.pop(); // 현재의 위치에 놓은 퀸은 다음에 놓을 퀸의 위치와 겹치는 부분이 생겨 놓을 수 없으니 제거한다.
		}
	}
	return res;
}
function isValid(oldPoints, newPoint) {
	let len = oldPoints.length;
	for (let i = 0; i < len; i++) {
		if (oldPoints[i][0] === newPoint[0] || oldPoints[i][1] === newPoint[1]) return false; // 현재의 퀸의 위치가 가로, 세로가 겹치는지 확인한다.
		if (Math.abs((oldPoints[i][0] - newPoint[0]) / (oldPoints[i][1] - newPoint[1])) === 1) return false; // 현재의 퀸의 위치가 대각선으로 겹치는지 확인한다.
	}
	return true;
}

---

후기

주변 지인의 추천으로 해당 알고리즘을 접하게 되었다.
평소 체스를 좋아했기에 흥미를 끄는데 성공하였다!
그렇다고 체스를 잘하는건 아니다...😝
가로,세로까지는 어떻게 생각은 하였으나...
대각선은 어떻게 해야할지 잘 몰랐다. 유튜브나 다른 사람의 풀이를 보고 저렇게 대각선을 구할수 있구나라는것을 알 수 있었다.
왜 머리가 이렇게 안돌아가는걸까...
해당 문제는 경우의 수를 구하는 문제지만 또 다른 문제로는
경우의 수가 아닌 방법을 그리는 문제가 있었다.