문제 푼 날짜 : 2021-09-18

문제

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

접근 및 풀이

개인적으로 좀 어렵게 푼 백트래킹 문제였다.
우선 퀸의 행마에 대해 알아야 했다.
퀸은 상,하,좌,우,대각 방향으로 행마할 수 있으므로 임의의 행에 하나의 퀸을 놓았을 때, 해당 행, 열, 그리고 모든 대각방향에는 다른 퀸을 놓을 수 없다.
이러한 사실을 이용하여 구현을 진행하였다.

1. 맨 처음 행부터 퀸을 놓는다. (코드 내에 1차원 배열 board 변수의 index는 행을 나타내고, 해당 값은 열을 나타낸다. ex) board[1] = 2 는 1행 2열에 퀸이 놓였다는 뜻이다.)
   1-1. 해당 위치에 퀸을 놓을 수 있는지를 체크해준다. (isPossible 함수)
   1-2. 이 때, 이전 행까지 놓인 퀸들의 위치를 보면서 같은 열에 있거나(board[row] == board[i])
   대각 위치에 있는지((abs(board[row] - board[i]) == row - i )) 체크해주었다.
2. 이렇게 진행하다가 N개의 퀸이 모두 놓였을 때, 퀸을 놓는 방법의 수를 하나씩 더해준다.

코드

// 백준 9663번 : N-Queen
#include <iostream>

using namespace std;

int N, ans = 0;
int board[16]; // idx : 행, 값 : 열

bool isPossible(int row) {
    for (int i = 0; i < row; i++) {
        if (board[row] == board[i] || (abs(board[row] - board[i]) ==  row - i )) {
            return false;
        }
    }
    return true;
}

void dfs(int row) {
    if (row == N) {
        ans++;
        return;
    }
    for (int col = 0; col < N; col++) {
        board[row] = col;
        
        if (isPossible(row)) {
            dfs(row + 1);
        }
    }
}

int main() {
    cin >> N;

    dfs(0);
    
    cout << ans;
    return 0;
}

결과

피드백

조금만 어려워지니 구현하는데 오래걸렸다.. 난이도가 높은 문제들도 많이 풀어봐야할 것 같다.