백준, BOJ, 9663번 C++ [CPP] **

전형적인 백트래킹 문제다.

백트래킹에 익숙하지 않은 터라 다른 사람풀이를 봐도 이해가 시간이 걸렸다.

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

9663번: N-Queen

 

---

 

백트래킹은 제일 인간다운 생각이 아닌가 싶다.

그리고 무의식적으로 그것이 효율적이라 생각하면서 쓰고 있다.

우선 나는 그렇다.

 

우선 이 문제를 보자마자 같은 줄에 못놓겠구나 생각이 들었다.

 

아무튼 거기까지만 하고 들어가보자

 

한줄에 하나 넣어보고 다음 줄에 되는 것 넣어보고 그 다음줄에 되는 것 넣어보고 하면 될 것같다.

되는 것만 넣어서 확인해보면 금방 할 것 같다. 

하지만 이것을 어떻게 컴퓨터가 알아듣게 하느냐가 문제였다.

 

코드의 주석을 보면서 이해해보자

 

#include<iostream>

using namespace std;

void init(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}

bool ischeck1[40]; // 세로
bool ischeck2[40]; // 우하향 대각선
bool ischeck3[40]; // 우상향 대각선

int cnt = 0;
int n;


//cur 행에 배치 (같은 줄에는 못놓는다)
void func(int cur){
    if(cur == n){ // 모두 배치할 수 있다면 그 배치는 조건에 부합한 배치
        cnt++;
        return;
    }
    // 현재 줄에서 놓을 수 있는 위치
    for(int i = 0; i<n; i++){
        if(ischeck1[i] || ischeck2[i+cur] || ischeck3[i-cur+n-1]) continue;
        
        //놓았다면 해당 퀸에 대해 공격경로를 막아놓음
        ischeck1[i] = 1;
        ischeck2[i+cur] = 1;
        ischeck3[i-cur+n-1] = 1;
        
        //해당 배치 상태에서 한 번더 배치
        func(cur+1);
        
        //이 라인을 읽는다는 것은 위의 배치가 끝나서 다음 배치로 넘어가기 전에 현 배치 상태에 대한 공격경로 무효
        //그래야 다음 배치를 하지
        ischeck1[i] = 0;
        ischeck2[i+cur] = 0;
        ischeck3[i-cur+n-1] = 0;
            
    }
    
}



int main(){
    init();
    cin >> n;
    func(0);
    cout << cnt;
    
}

 

 

여기서 핵심은 1가지다.

퀸의 공격경로를 어떻게 파악할 것인가?

누적되는 공격경로를 어떻게 파악할 것인가??

 

퀸의 공격경로는 가로, 세로, 대각선이 있다. 

하지만 현재 줄에 1개만 놓을 수 있다는 것을 조건에 두었기 때문에

가로는 고려하지 않고 세로만 고려한다.

 

n=4라고 해보자

 

0,0	0,1	0,2	0,3
1,0	1,1	1,2	1,3
2,0	2,1	2,2	2,3
3,0	3,1	3,2	3,3

 

세로를 보자 1, 1에 두면 y값이 1이라면 퀸이 들어갈 수 없다.

우하향 대각선을 보자 0,0 / 2,2 / 3,3 에 퀸이 들어갈 수 없다.

우상향 대각선을 보자 2,0/ 0,2 에 퀸이 들어갈 수 없다.

 

그렇다면 이것을 어떻게 저장할 수 있느냐??

 

세로부터 보자 y값이 가질 수 있는 범위는 n과 같다 1-15이다. 16칸의 배열을 만들면 저장할 수 있다.

즉, 어느 좌표를 넣는다고 했을 때, 그 좌표의 y 값을 저장한다면 다른 좌표를 넣을 때 이미 저장된 y좌표의 값을 넣지 못하게 하면 된다.

 

우하향을 보자

x,y 좌표의 합이 같은 것이 특징이 아니다. 서로 x-y값이 같다는 것이 특징이다.

. n는 1-15 범위다 그렇다면  x,y는 0-14까지 가질 수 있다. 하지만 x-y의 범위는..? (14-0)~(0-14)가 되겠지..? 

 

하지만 우하향에서 음수가 나올 수 있다. 그래서 음수가 나올 때 그만큼 올려줘야 한다.

때문에 n-1 만큼 더해줘서 이용한다. 

때문에 40칸 정도면 충분하다

 

 

우상향을 보자

x,y좌표의 합이 같은 것이 특징이다.

 

 

하지만 메모리 제한을 보면 모두 40칸해도 충분하다.

 

백트래킹은 이렇게 한다.

1. 어떤 순서로 넣을 지 생각해본다

2.  넣었을 때 다음 선택에 영향을 미친다면 어떻게 적용시켜줘야 하는가?

3. 계속 돌린다.

 

끝. 간단하지만 여기선 2번 다음 선택에 어떻게 영향을 주느냐? 를 어렵게 주어서 이 문제가 어려워졌다.