[백준(BOJ)] 9663번 N-Queen C++

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

9663번: N-Queen

 

 

어떤 문제인가?

백 트랙킹의 대표적인 문제로 들었다.

N * N 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 물어보는 문제이다.

 

접근 방법

N이 4일 때 (1, 1)부터 퀸을 놓으면서 진행한다.

퀸은 대각선과 직선을 모두 공격할 수 없으므로 한 줄에 퀸이 놓이면 무조건 다음 줄로 넘어가야 한다.

그래서 두 번째 줄로 이동해서 다음 퀸을 놓을 자리를 찾는다.

(2, 1), (2, 2)는 공격이 가능하므로 (2, 3)에 두 번째 퀸을 놓고 세 번째 줄로 이동한다.

 

(2, 3)에 놓고 세 번째 줄로 이동했을 때는 놓을 수 있는 위치가 없다. 

따라서 다시 두 번째 줄로 돌아가 (2, 4)로 두 번째 퀸을 재배치한다.

그리고 다시 세 번째 줄로 이동한다.

이번에는 (3, 2)에 세 번째 퀸을 놓고 네 번째 줄로 이동한다.

하지만 퀸을 배치할 수 있는 위치가 없다.

따라서 (3, 2)에도 퀸 배치 불가 + (2, 4)에도 퀸 배치 불가 = > (1, 1)에도 퀸 배치 불가

 

정리하자면

먼저 (1, 1)부터 탐색을 시작해서

퀸 배치 -> 다음 줄 이동 -> 퀸 배치 -> 다음 줄 이동

위 과정을 반복해서 맨 마지막 줄에 퀸을 배치할 수 있다면 그 경우가 가능한 경우인 것이다.

 

int n;
int arr[16];
int cnt = 0;

문제에서 필요한 변수와 정수형 배열이다.

배열은 퀸의 위치를 저장하는 용도로 쓰이고 cnt는 경우의 수를 카운트하는 것이다.

 

bool isPossible(int y, int x) {
    for (int i = 1; i < y; i++) {
        if (arr[i] == x || abs(arr[i] - x) == abs(y - i)) {
            return false;
        }
    }
    return true;
}

void nQueen(int y, int x) {

    if(y==n+1){
        cnt++;
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (isPossible(y, i)) {
            arr[y] = i;
            nQueen(y + 1, x);
        }
    }
}

int main() {
    cin >> n;
    nQueen(1, 1);
    cout << cnt;
}

 

퀸을 해당 위치에 놓을 수 있을지 판단하는 isPossible함수와 경우의 수를 카운트할 nQueen함수가 존재한다.

 

isPossible함수는 x, y좌표를 매개변수로 넘겨받아 연산을 한다.

첫 번째 줄부터 y-1번 줄까지 반복문을 돌며 직선상에 있는지 대각선 상에 있는 지를 판단한다.

 

nQueen함수도 마찬가지로 x, y좌표를 매개변수로 넘겨받아 연산을 한다.

탈출 조건은 y == n +1이다.

이게 무슨 뜻이냐면 재귀를 통해 퀸이 마지막 줄까지 도달했다는 뜻이다.

이 뜻은 해당 경우가 가능한 경우라는 뜻이다.

따라서 cnt를 증가시켜주고 함수를 끝낸다.

 

연산은 1부터 n까지 반복문을 돈다.

이때 is는 x좌표를 의미한다.

isPossible함수로 해당 위치가 배치 가능한지 확인한다.

만약 배치가 가능하다면 위치를 저장해주고 다음 줄(y+1)로 이동한다.(재귀를 통해 함수를 호출한다.)

 

마지막으로 계산된 경우의 수 cnt를 출력해주면 된다.

 

무엇이 어려웠는가?

백 트랙킹을 이번에 처음 배웠고, 배운 내용을 바탕으로 풀어본 첫 번째 백 트랙킹 문제이다.

이론으로는 감이 잡혔지만 이를 코드로 구현하는 것이 어려웠다.

 

처음에는 이차원 배열을 사용해 퀸을 배치할 때마다 일일이 퀸의 공격 범위를 표시하려고 했다.

하지만, 이 방식을 사용한다면 만약 퀸을 배치하고 다음 줄로 넘어가다가 결국은 이 경우가 유망하지 않다면

체스판을 모두 원상태로 돌려놔야했다.

구현이 굉장히 복잡할뿐더러 백 트랙킹의 방식에 적합하지 않다고 생각했다.

감이 잡히지 않아서 선배님께 도움을 받았다. 선배님께서 선배님의 코드를 설명해주셨고 이를 바탕으로 문제를 풀어나갔다.

선배님의 코드가 정확하게 기억나지는 않지만, 아마 거의 비슷할 것이라고 생각된다.

 

배운 점

재밌다. 정말 이상하게 들릴 수도 있지만 재밌다.

이제야 제대로 알고리즘다운 알고리즘 문제를 풀기 시작했다.

아직 부족한 부분이 많기에 어렵다.

하지만 재밌어서 다행이다. 재밌는 게임을 1 렙부터 키우는 느낌이다.

재미없는 게임을 하는 것은 말도 안 된다. 

알고리즘이 내가 재밌다고 생각하는 게임이라고 느껴져서 다행이다.

재밌는 게임이라면 쪼렙의 나약한 모습은 만렙이 되었을 때를 생각하며 버틸 수 있다.

빨리 성장한 내 모습을 느껴보고 싶다.

 

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/%EC%99%84%EC%A0%84%ED%83%90%EC%83%89%20%26%20%EB%B0%B1%ED%8A%B8%EB%9E%99%ED%82%B9/9663.cpp

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.