백준 9663번 - N-Queen

백준 9663번 - N-Queen

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

9663번: N-Queen

이 문제는 백 트래킹 알고리즘 문제이다.

백 트래킹에 대해서 공부하다 보니 백 트래킹의 가장 기본 문제라고 하여서 풀어보았다.

 

공부하고 풀었는데도 생각보다 어려웠다.

처음에는 2차원 배열로 놓고 모든 지점의 좌표에서 dfs를 돌릴 생각이었는데

생각보다 너무 지저분한 것 같아서 다른 방법을 생각해보다가 구글링을 통해서 알아낸 방법으로 풀었다.

 

분명 2차원 배열로도 풀 수 있겠지만

1차원 배열로 간단하게 풀 수 있는 방법이 있다.

바로 열 배열만 잡고, 0행부터 시작해서 각 행의 가결을 for문을 통해 찾아가며 퀸을 놓을 수 있는지 없는지 판단한다.

 

쉽게 말해 0행 0열부터 시작해서 0행 0열에 퀸을 놓는다고 가정하면

1행에서 놓을 수 있는 위치를 재귀를 통해 다시 탐색한다.

이때 가장 중요한 포인트는 이전에 퀸들이 놓인 열들을 저장하여 퀸이 놓일 수 있는지 없는지를 판단해주는 것이다.

만약 퀸이 놓일 수 없는 자리라면 백 트래킹 기법으로 뒤로 돌아가서 다시 dfs탐색을 한다.

 

처음에 말로만 들었을 때는 쉽게 구현할 수 있겠구나 생각했는데 막상 풀어보니 쉽진 않았다.

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int n;
int colum[17];
int ans = 0;
 
bool okay(int r) {
    for (int c = 0; c < r; c++) {
        if (colum[r] == colum[c] || (r - c) == abs(colum[r] - colum[c])) return false;
        // r행(현재 퀸을 놓은 위치)의 열과 기존의 열들을 비교, || 대각선 비교(이 때 r-c는 무조건 양수)
        // 조건 불만족시 그 위치에는 퀸이 놓일 수 없으므로 false 반환
    }
    return true;
}
 
void dfs(int row) {
    if (row == n) {
        ans++;
        return;
    }
    for (int col = 0; col < n; col++) {//row행에서의 각 열들을 돌며 퀸을 놓을 위치를 찾음.
        colum[row] = col;
        if (okay(row)) { //퀸이 이 위치에 놓일 수 있는지 판단.
            dfs(row + 1);//조건을 만족한다면 현 위치에 퀸을 놓고 다음 행으로 넘어감(재귀)
        }
    }
}
 
int main() {
    scanf("%d", &n);
    dfs(0);
    printf("%d\n", ans);
}