백준 9663번 - N-Queen

 

 

 

* 문제 링크

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

 

 

 

문제 내용 요약

 

N * N 체스판 위에 서로의 공격 범위에 닿지 않게 퀸 N 개를 놓는 방법의 갯수를 출력해라 ( 1 ≤ N ≤ 14 )

 

 

 

 

 

접근법

 

일단 체스를 모르는 사람이 있을 수도 있으니 체스와 퀸에 대해 먼저 알아보자

 

체스를 좋아하긴 하다만 M e g a c h e s s a t r o n

 

그놈의 캐슬링 앙파상 뭐시기 오픈 뭐시기 뭐시기 너무 많다. (그리고 잘 알지도 못함)

 

정말로 체스에서의 퀸에 대한 설명만 할 것이다.

 

문제 하나 풀려고 굳이 체스 전체를 설명하고 싶지는 않다.

 

퀸은 무조건 지켜야하는 킹 빼고 가장 중요한 말이라고 생각한다.

 

범위가 가장 사기이기 때문에

 

무려 룩 + 비숍이라는 사기적인 스펙을 가지고 있다.

 

그래서 공격 범위는 아래와 같다.

 

사기챔

 

가로, 세로 및 대각선 몇 칸이든 이동이 가능하다.

 

이 넓은 공격 범위를 보아라

 

정말 사기 그 자체라고 할 수 있다.

 

 

 

이제 백트래킹의 개념을 알아보기 위해서, 단순하게 브루트포스를 이용한다고 생각해보자.

 

최대 N인 14를 넣는다고 생각하고 얼마나 많은 연산이 필요한지 얼추 느껴보자. (대충 계산)

 

 

1. 모든 칸 아무데나 퀸을 넣고 되는지 확인하기 =  196 * 195 * 194 * ... * 183 / 14! = 880,530,516,383,349,192,480

 

2. 가로줄에 하나씩만 되니까 반영하기 = 14^14 = 11,112,006,825,558,016

 

3. 세로줄에도 하나씩만 되니까... = 14! = 87,178,291,200

 

4. 대각선도... 하기에는 어차피 가능한 위치를 계산해야하니 큰 의미는 없다.

 

보통 문제를 해결하는 시간을 위한 연산은 1억 번 정도로 두고 한다는 것을 생각하면 턱 없이 많다.

 

 

 

이를 충분히 의미있는만큼 줄이는 방법이 바로 '백트래킹'이다.

 

간단하게 말하자면, "안되면 돌아가자" 정도로 생각하면 되겠다.

 

다만 이 "되는지 안되는지"를 최대한 효율적으로 구하는 것이 중요하다.

 

그것에 따라 연산 횟수가 달라질테니

 

그래서 구현 방식에 따라 백트래킹을 해도 시간이 초과되는 경우도 있으니 조심해야한다.

 

 

 

그럼 어떻게 확인할지를 생각해보자.

 

사람들마다 과정의 차이가 존재할 수 있음은 감안하자.

 

나는 다음과 같은 과정으로 접근했다.

 

 

1. 어차피 가로줄에 하나의 퀸만 놓을 수 있으니 현재 놓는 퀸의 개수로부터 현재 가로줄을 알 수 있다.

    가로줄에 놓을 때 몇 번째 열에 놓였는지를 저장한다.

 

2. 세로줄에도 하나만 가능하니, 각 열 별로 퀸이 있는지를 확인하는 배열을 따로 만든다.

 

3. 다음 줄에 퀸을 놓을 때, 해당 열에 놓을 수 있는지와, 전에 놓였던 퀸과 대각선으로 만나는지 확인한다.

    1번의 배열을 이용해서 열 차이와 행 차이가 같은지를 확인하는 것으로 대각선을 확인한다.

 

4. 가능하면 다음 퀸을 놓고, 불가능하면 지금 퀸의 위치를 다음으로 바꾼다. N개의 퀸이 놓여지면 가능한 방법이다.

 

 

그렇게 해서 백트래킹을 구성하면 해결된다.

 

다른 좋은 방법이 있을 수도 있으니 생각해보는 것도 괜찮을 것 같다.

 

나는 이거 말고는 생각 안 해봤다.

 

 

 

 

백트래킹할 때 주의점

 

 

중간에 돌아갈 때 기존 변수의 값이 잘못된 영향을 주는 경우를 차단하자.

 

혹시 분명 잘 구성했는데 틀렸다고 한다면 이런 경우가 있을 수 있다.

 

 

시간 초과가 위의 경우에도 나타날 수 있지만,

 

방법 자체가 시간이 오래 걸리는 경우가 많으니 다시 생각해보자.

 

예를 들자면, 체스판에 퀸을 놓을 수 있는 위치를 일일이 바꾸는 식의 구성을 했다던지...

 

그런 오래 걸리는 방법을 쓰지 않았는지 잘 생각해보자.

 

 

 

 

내 코드

#include <iostream>
#include <cmath>
using namespace std;

int n,sum=0;
int v[16];
bool vstd[16];

void f(int a) {
    if(a==n) {
        sum++;
        return;
    }
    for(int i=0;i<n;i++) {
        if(vstd[i]==0) {
            if(a==0) {
                vstd[i]=1;
                v[a]=i;
                f(a+1);
                vstd[i]=0;
            }
            else {
                int ok=1;
                for(int j=0;j<a;j++) {
                    if(a-j==abs(v[j]-i)) {
                        ok=0;
                    }
                }
                if(ok) {
                    vstd[i]=1;
                    v[a]=i;
                    f(a+1);
                    vstd[i]=0;
                }
            }
        }
    }
}

int main() {
	scanf("%d",&n);
	f(0);
	printf("%d",sum);
}

옛날에 백트래킹 배울적에 짰던 코드라 최적화가 덜 되어있다.

 

특히 저 끔찍한 if else 의 연쇄를 보자.

 

지금보니 정말 끔찍하다.

 

코드를 짤 때 좋지 않은 방식이니 웬만해서 3번 이상의 연쇄로 구성하지는 말자.