[프로그래머스 lev2/JS] N-Queen

문제 출처

프로그래머스 lev2 - N-Queen

나의 풀이

대각선 판별 지점에서 막혔다.
하나하나 다 판별하기엔 너무 비효율적인데..

다른 풀이 (c++)

N-Queen은 대표적인 백트래킹 문제라고 한다.
체스 말을 첫행부터 한행씩 두고 dfs를 진행하다가 더 이상 진행이 안 될 때 다시 돌아와서 그 다음 행을 둔다.

2차원 배열로 풀지 않아도 된다.

(1)
1차원 배열 board을 생성하고,
board의 index를 ⇒ y좌표(혹은 x좌표)로,
board의 element를 ⇒ x좌표(혹은 y좌표)로 설정한다.

그리고 board의 첫번째 index부터 값을 하나씩 넣어 놓고 재귀함수를 진행하는 하나의 반복문(while)을 순회한다.

(2)
재귀함수 path에서는
y가 n과 같아지면, 1차원 배열 board를 전부 채웠다는 의미이므로 cnt++해주고 종료한다.

체스의 퀸은 가로/세로/대각선이면 어디든 움직일 수 있다.

• 여기에 해당하면 break해서 재귀를 멈춰야 한다.
  => 가로/세로 : board[j] == i
  => 대각선 : 대각선에 있다면 기울기가 1이므로 abs(y-j) == abs(i-board[j])
• 해당하지 않는다면 재귀를 호출해서 y가 n에 도달할 수 있게 해준다.

#include <iostream>
#include <cmath>

#define MAX_SIZE 8
// 최대 MAX_SIZE queen 문제까지 해결할 수 있다.

using namespace std;

int board[MAX_SIZE];
// board[i]는 i번째 행에 퀸이 몇번째 열에 있는지 의미하는 변수이다. (행열은 서로 바뀌어도 된다.)
// 즉 board[0] = 3일때, (1,4) 혹은 (4,1) 위치에 퀸이 있다는 뜻이다.
int n;
int cnt;

void path(int y) {
	// y는 현재 몇개의 퀸이 배치되었는지를 의미하는 변수다.
	int ko;
	if( y == n ) {
		// n개의 퀸이 배치가 되었다면 이 경우는 답이다.
		cnt++;
		return;
	}
	for( int i=0; i<n; i++ ) {
		// ko는 퀸이 배치될 수 있는지를 저장하는 플래그다.
		ko = 1;
		for( int j=0; j<y; j++ ) {
			// 이미 배치가 끝난 퀸을 참고해서 i번째 칸에 퀸을 설치할 수 있는지를 확인한다.
			if( board[j] == i || abs(y-j) == abs(i-board[j]) ) {
				// j번째 줄에 있는 퀸과 같은 칸에 있거나, 대각선에 같은 곳에 있다면, i번째 칸에 대한 탐색을 중단한다.
				ko = 0;
				break;
			}
		}
		if( ko ) {
			// 여기까지 왔다면 y번째 줄에 i번째 칸에 퀸을 놔두는 것이 가능하다.
			board[y] = i;
			path(y+1);
		}
	}
}

int main() {
	int k;
	cin >> k;

	while( k-- ) {
		cin >> n;
		cnt = 0;
		path(0);

		cout << cnt << '\n';
	}

	return 0;
}

이러한 재귀 원리를 사용해서 공식처럼 구현되어 있기도 하다.

function solution(n) {
    return [1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596][n - 1]
}

다른 풀이 2 (js)

마찬가지 백트래킹 풀이를 js로 구현한 코드

function solution(n) {
  let answer = 0;
  
  const dfs = (board, row) => {
    if(row === n) answer++;
    else {
      for(let i = 1; i <= n; i++) {
        board[row+1] = i;
        if(isValid(board, row+1)) dfs(board, row+1);
      }
    }
  }
  
  const isValid = (board, row) => {
    for(let i = 1; i < row; i++) {
      if(board[i] === board[row]) return false;
      if(Math.abs(board[i] - board[row]) === Math.abs(i - row)) return false;
    }
    return true;
  }
  
  for(let i = 1; i <= n; i++) {
    const board = new Array(n+1).fill(0);
    board[1] = i;
    dfs(board, 1);
  }
  
  return answer;
}

참고

여덟 퀸 문제