백준 9663번: N-Queen

배영채·2022년 1월 28일
0

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

참고한 블로그 : https://chanhuiseok.github.io/posts/baek-1/



백트래킹 문제의 기본이라고 하는 N-Queen 문제이다. N x N 크기의 보드에 N개의 퀸을 놓을 때 서로 공격하지 못하게 놓을 수 있는 모든 경우의 수를 구하는 문제이다.

처음에 내가 생각해서 푼 방법은 아직 방문하지 않은 보드 칸을 찾아서 행, 열, 대각선이 같은 칸을 visit으로 체크하고, 그 다음 방문하지 않은 칸을 찾아서 수를 세는 것을 반복하는 것으로 했다.
코드는 문제 없이 돌아가고 답도 잘 나와서 제출했는데 시간초과가 떴다. 시간을 줄일 방법이 생각나지 않아서 검색을 해서 코드를 짰다.

우선 N x N 보드이길래 당연히 2차원 배열로 선언을 해서 visit 표시를 했었는데 블로그에서 1차원 배열로 표현을 할 수 있다고 했다.
4 x 4 크기라고 한다면 원래 2차원 배열로 표현할 때 board[0][1] = 1이면 0행 1열에 퀸이 놓인다는 뜻이다.
이것을 1차원 배열로 표현하면 board[0] = 1로 둘 수 있다. 인덱스가 행, 배열의 값이 열을 표현하는 것이다. 다른 예시로 2행 0열에 퀸이 놓여있다고 하면 board[2] = 0로 쓸 수 있다.

다음으로 칸에 퀸을 놓을 수 없는 경우를 생각하면
1. 다른 퀸과 같은 행이나 열에 놓이는 경우
2. 다른 퀸과 대각선에 놓이는 경우

같은 행에 놓이는 것은 1차원 배열에 값이 있는 경우 넣지 않는 것으로 해결할 수 있고, 같은 열에 놓이는 것은 배열의 값이 같지 않으면 된다.
대각선으로 놓이는 것은 행의 차이와 열의 차이가 같은지를 비교해서 판단할 수 있다. (행의 차 == 열의 차) 이면 대각선에 놓이는 경우이다.

위의 모든 경우를 생각해서 코드를 짜면 다음과 같다.
<작성한 코드>

#include <iostream>
#include <cstdlib> // abs를 쓰기 위한 헤더
#include <vector>
using namespace std;

int n, cnt;
vector<int> board(15, -1); // -1로 초기화, 비어있다는 뜻

int pruning(int idx){
    for(int i = 0; i < idx; i++){
        if(board[i] == board[idx] || abs(i - idx) == abs(board[i] - board[idx])){
            // 열 값이 같거나 대각선에 있는 경우 놓으면 안됨
            return 0;
        }
    }
    return 1;
}

void dfs(int idx){
   if(idx == n){ // 맨 마지막 행까지 찾았으면 퀸을 다 놓은 것 -> 값 ++
       cnt++;
       return;
   }
   for(int i = 0; i < n; i++){ // idx행의 0 ~ n-1 자리에 퀸을 놓을 것
       board[idx] = i;
       if(pruning(idx)){ // 검사했을 때 놓아도 되는 곳이면 다음 행으로 넘어감
           dfs(idx + 1);
       }
   }
}

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

0행부터 n - 1행까지 순서대로 퀸 자리를 찾아가면 답이 나온다. 주석을 보면서 따라가보면 이해가 될 것이다.
방법을 생각해내는게 너무 어렵다.. 열심히 훈련을 해야겠다.

0개의 댓글