[백준] N-Queen 9663 (Gold 4) - C++

 

문제 링크 : https://www.acmicpc.net/problem/9663

문제 요약

N×N 체스판 위에 N개의 퀸을 서로 공격하지 않도록 배치하는 문제다.
퀸은 가로, 세로, 대각선 방향으로 모두 공격할 수 있다.

결국 조건은 이거다.

• 같은 행에 두 개 있으면 안 되고
• 같은 열에 두 개 있으면 안 되고
• 같은 대각선 위에 있어도 안 된다

---

풀이 사고 과정

이 문제는 조금만 생각해보면 형태가 단순해진다.

각 행에는 어차피 퀸을 하나씩만 놓으면 된다.
그렇다면 문제는 이렇게 바뀐다.

각 행에 하나씩 퀸을 두되,
열과 대각선이 겹치지 않도록 배치하라.

 

이제 “행”은 깊이(depth)로 보고,
각 depth마다 “어느 열에 둘 것인가”를 결정하면 된다.

그래서 자연스럽게 백트래킹을 떠올렸다.

첫 번째 행에서 가능한 열에 하나 놓고,
두 번째 행으로 내려가서 또 가능한 열을 찾는다.
조건을 위반하면 그 가지는 더 내려가지 않는다.
마지막 행까지 내려가면 경우의 수를 1 증가시키고 돌아온다.

 

2차원 배열을 쓰지 않은 이유

처음에는 체스판 전체를 2차원 배열로 관리할까 생각했다.
그런데 그건 비효율적이다.

매번 퀸을 놓을 때마다 체스판 전체를 탐색해야 한다.
어차피 우리는 “각 행에 하나씩만 둔다”는 전제를 깔고 있다.

그렇다면 필요한 정보는 이것뿐이다.

“각 열에 몇 번째 행에 퀸이 놓여 있는가?”

그래서 1차원 배열 하나로 해결했다.

arr[행] = 열

이렇게 두면,

• arr[0] = 1 → 0행 1열에 퀸
• arr[1] = 0 → 1행 0열에 퀸
• -1이면 아직 배치 안 된 상태

 

대각선 검사 아이디어

퀸은 대각선 공격도 가능하다.

대각선에 있다는 건 무엇을 의미할까?

행 차이와 열 차이가 같으면 대각선이다.

abs(현재행 - 이전행) == abs(현재열 - 이전열)

이 조건이 성립하면 대각선에 있는 것이다.

그래서 유효성 검사는 이렇게 한다.

1. 같은 열인지 확인
2. 대각선 조건 확인

이 두 개만 통과하면 배치 가능하다.

---

전체 코드 흐름

backtracking(d)

    만약 d == N 이면
        경우의 수 증가
        return

    for i = 0 ~ N-1
        i열에 놓을 수 있는지 검사

        모든 이전 행 j에 대해
            같은 열이면 실패
            대각선이면 실패

        가능하면
            arr[d] = i
            backtracking(d+1)

행을 하나씩 내려가면서 가능한 열을 고르고,
끝까지 내려가면 경우의 수를 더하는 구조다.

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

int N;
vector<int> arr;
int result=0;
void backtracking(int d){
    if(d==N){  //N개의 행에 배치 완료
//경우의 수 1 증가, 함수 반환
        result++;
        return;
    }

    for(int i=0;i<N;i++){ //각 열 탐색
        //i번째 열에 퀸 배치할 수 있으면 배치하기
        bool can_place=true;
        for(int j=0;j<d;j++){
        //세로 공격 방어 : 어차피 위의 행부터 배치해서 같은 행에 배치할 일은 없음
        //가로 공격 방어 : i랑 같은 거 존재시 X
        // 대각선 공격 방어 : index 차이랑 안에 저장된 값 차이랑 같으면 X
            if(arr[j]==i || abs(d-j)==abs(i-arr[j])){
                can_place=false;
               break;
               break;// 한 번이라도 걸리면 더 검사할 필요 없음
            }
        }
        if(can_place){
            arr[d]=i;
            backtracking(d+1);
        }
        //배치 가능하면 d++ 해서 재귀함수 호출
    }
    return;

}

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

    cin>>N;
    arr.assign(N,-1);

    backtracking(0);

    cout<<result;
    return 0;
  
}

---

시간 복잡도

이론적으로 보면 N개의 자리에서 순열을 만드는 것과 비슷하다.
최악의 경우는 거의 O(N!)에 가깝다.

하지만 가지치기를 계속 하기 때문에 실제 연산은 훨씬 줄어든다.