백준(BaekJoon) 9663 : N-Queen c++

▶문제 : 9663번: N-Queen (acmicpc.net)

9663번: N-Queen

 

▶코드 작성

#include <iostream>
#include <cstdlib>

int board[16]; //배열 자리 : 가로칸 , 배열값 : 세로줄
int len, cnt;

void chess(int n) {//n : 세로줄(배열값)
    bool t;

    if (n == len + 1) {//마지막줄의 퀸 자리가 정해지고 재귀함수가 호출되면 n==len+1 이다.
        cnt++;//퀸 자리가 정해졌으므로 더해줌
        return;
    }

    for (int i = 1; i <= len; i++) {//가로줄 확인
        if (board[i] == 0) {//가로줄에서 자리가 비어있는 곳 찾기
            t = true;//비어있는 자리에 들어가도 되는지 판별
            for (int j = 1; j <= len; j++) {
                if (board[j] > 0) {//가로줄에서 이미 자리잡은 퀸 찾기
                    if (abs(j - i) == n - board[j]) {//먼저 자리잡은 퀸이 대각선으로 잡히는지 확인
                        t = false;//들어가면 안되는 자리
                        break;
                    }
                }
            }
            if (t == true) {//대각선으로 안잡히는 자리라면
                board[i] = n;//퀸 대입
                chess(n + 1);//재귀함수로 다음 퀸 자리를 찾기
                board[i] = 0;//처음으로 돌아가기
            }
        }
    }
}

int main() {
    std::cin >> len;
    chess(1);//첫 째줄부터 시작
    std::cout << cnt;
}

 

▶해석

체스판을 생각하면 2차원 배열을 이용해 풀 수 있지만 문제는 퀸만을 사용한다.

퀸은 가로, 세로, 대각선 세가지만 고려하면 된다.

때문에 가로, 세로를 간단하게 생각하면 2차원 배열을 1차원 배열로 생각할 수 있다.

 

	Q-1			첫 째줄
			Q-2	둘 째줄
Q-3				셋 째줄
		Q-4		넷 째줄

2차원 배열로 만든 n = 4일 때 퀸이 서로 잡히지 않는 체스판이다.

여기서 봐야 할 부분은 퀸은 가로줄과 세로줄 둘 다 겹치지 않는다는 것이다.

따라서 세로줄을 겹치지 않게 간단히 하면서 가로줄을 구분하도록 하기 위해 다음과 같이 1차원 배열로 나타낼 수 있다.

 

Q-3

Q-1

Q-4

Q-2

board배열로 선언하고 세로줄이 겹치지 않으므로 칸마다 퀸 하나씩 무조건 배치되어있다.

또한 세로줄을 나타내기 위해 배열 값을 세로줄의 칸 번호로 지정해준다.

board [0] = 3 : 세 번째 줄 퀸

board [1] = 1 : 첫 번째 줄 퀸

board [2] = 4 : 네 번째 줄 퀸

board [3] = 2 : 두 번째 줄 퀸

 

이런 식으로 1차원 배열로 나타내서 풀이하면 퀸의 가로, 세로 움직임은 고려할 필요가 없어진다.

이제 대각선 움직임을 피해 퀸을 배치하면 되는데 일단 생각해본 공식은 이러하다.

if (abs(j - i) == n - board[j]) {
    t = false;
    break;
}

board배열의 j자리에 있는 퀸과 아직 퀸이 없는 i자리를 비교해 두 자리가 대각선으로 만나면 false로 바꾸고 종료한다.

 

		Q-1
Q(A)-3				Q(B)-3

첫 번째 줄에 퀸이 board [2]에 있다. 여기서 계산을 편하게 하기 위해 board [3]에 있다고 생각한다

(실제로 for문도 j = 1부터 시작한다)

표를 보면 세 번째 줄의 Q(A)와 Q(B) 둘 다 Q1과 대각선으로 만난다.

여기서 주의깊게 볼 부분은 대각선으로 만나는 공간을 사각형으로 보면 정사각형이라는 것이다.

그래서 Q(A)부터 보면 Q1과 Q(A)의 가로의 차는 Q(A)(가로) - Q1(세로) = 1 - 3 = -2이고,

세로의 차는 Q(A)(세로) - Q1(세로) = 3 - 1 = 2이다.

정사각형이기 때문에 가로의 차를 절댓값으로 계산해 세로의 차와 같다면 대각선으로 만난다는 것이다.

 

마찬가지로 Q(B)와 Q1의 가로의 차는 Q(B)(가로) - Q1(가로) = 5 - 3 = 2이고,

세로의 차는 Q(B)(세로) - Q1(세로) = 3 - 1 = 2이다.

가로의 차와 세로의 차가 같으므로 대각선으로 만난다는 것이다.

 

따라서 위처럼 조건을 if문으로 만들어 대각선으로 만나는 경우를 제외한 모든 배치는 서로 만날 수 없는 배치인 것이다.