[C++] Boj 9663 N-Queen

문제 링크

9663 N-Queen

---

접근

역시 백트래킹 연습 문제이다. 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제인데, 중요한 건 나는 체스의 룰을 모른다. 그래서 퀸의 이동 규칙을 찾아봤다.

 

퀸의 이동 규칙

 

• 퀸은 상하좌우 맨 끝까지 이동할 수 있다.
• 퀸은 4방향 대각선 맨 끝까지 이동할 수 있다.

---

문제 적용

N x N  체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이므로, 일단 같은 행에는 1개의 퀸만이 위치할 수 있다는 걸 알 수 있다. 이렇게 규칙을 찾아보면,

 

 

• 퀸은 다른 퀸과 같은 행에 있을 수 없다.

 

• 퀸은 다른 퀸과 같은 열에 있을 수 없다.

 

• 좌측 하단과 우측 상단을 연결하는 대각선이 있고  (x, y)에 퀸이 있을 때 x + y의 값이 n이라고 하자.
• 그렇다면 다른 퀸은 x' + y' = n인 좌표에 있을 수 없다.
• 같은 대각선이라는 뜻이므로.

 

 

• 마찬가지로 좌측 상단과 우측 하단을 연결하는 대각선이 있고 (x, y)에 퀸이 있을 때 x - y의 값이 n이라고 하자.
• 그렇다면 다른 퀸은 x' - y' = n인 좌표에 있을 수 없다.

 

이제 이 좌표를 isUsed 표시를 해서 백트래킹을 해 주면 된다!

---

코드

#include<iostream>
using namespace std;

// 같은 열인지 확인
bool isUsed0[30];

// 같은 ↗ 대각선 상에 있는지 확인
bool isUsed1[30];

// 같은 ↘ 대각선 상에 있는지 확인 
bool isUsed2[30];

// 1 <= n < 15
int n;

int cnt;

// curX번째 행마다 퀸을 하나씩 배치 예정
void Solve(int curX)
{
    if (curX == n)
    {
        cnt++;
        return;
    }

    // (curX, i)에 퀸을 놓는다.
    for (int i = 0; i < n; i++)
    {
    	// curX - i + n - 1 는 index out of range 방지
        if (isUsed0[i] || isUsed1[curX + i] || isUsed2[curX - i + n - 1]) continue;
        isUsed0[i] = true;
        isUsed1[curX + i] = true;
        isUsed2[curX - i + n - 1] = true;
        Solve(curX + 1);
        isUsed0[i] = false;
        isUsed1[curX + i] = false;
        isUsed2[curX - i + n - 1] = false;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    Solve(0);

    cout << cnt;

    return 0;
}

---

참고

바킹독