[9663] N-Queen

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

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1

예제 출력 1

백트래킹이란, 모든 가능성을 조사하지 않고는 해를 구할 수 없는 경우가 존재하는 문제에서, 모든 가능성을 조직적이고 효율적인 방법으로 조사하는 알고리즘 설계 방식이다. 이때, 조사하지 않아도 되는 부분은 조사 대상에서 제외하여 해를 더 빨리 찾는다.

그리고 이러한 백트래킹은 DFS의 변형이다.

이러한 백트래킹의 가장 대표적인 문제가 바로 N-Queen 문제이며, 이 문제는 다소 어렵고 난해하다. 하나하나 살펴보자. 이번 포스팅에서는 두 가지 방법을 사용해보고 비교해보며 좀 더 심층적으로 공부한다.

백트래킹을 구현할때 먼저 생각해야 하는 부분은 다음과 같이 정리해볼 수 있다.

상태 정의 및 제약 조건 파악
종료 조건 설정
재귀적 분기 및 가지치기
탐색 및 복구

조금 더 쉽게 이야기해보면 다음과 같이 표현할 수 있다.

선택
탐색
- 종료 - 성공
- 종료 - 실패/가지치기
복구/백트래킹

이를 바탕으로, 문제를 분석하고 해결해보자.

1. 상태 정의 및 제약 조건 파악 - 각 단계(depth)에서 어떤 정보가 유지되어야 하는가?

i) N-Queen 문제의 목표와 전략

목표: N * N 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치한다.
기본 전략: 한 줄에 퀸을 하나씩만 놓는다.
Depth(단계): 현재 몇 번째 줄에 퀸을 놓을 차례인가?
- depth = 0: 0번 줄에 퀸을 놓을 차례
- depth = 1: 1번 줄에 퀸을 놓을 차례
- ...
- depth = N: N개의 퀸을 모두 놓았다 -> 종료조건 - 성공

ii) 상태 정의: 무엇을 기록해야 하는가?

depth번째 줄, 즉 depth번 줄에 퀸을 놓으려고 한다. 가령, N = 4이고, 현재 depth = 2에 퀸을 놓을 차례라고 가정해보자.

depth = 0 일 때: 퀸을 (0, 1)에 놓았다.
depth = 1 일 때, 퀸을 (1, 3)에 놓았다.

이제 depth = 2의 0,1,2,3 중 어디에 퀸을 놓을지 결정해야한다. 그렇다면, depth = 2인 입장에서, (2, j)에 퀸을 놓아도 되는지 판단하려면 어떤 정보가 필요할까? 바로, '앞선 줄들(0, 1번 줄)에 퀸이 어디에 놓여있는가?' 이다. 즉, 앞선 퀸들의 위치 정보가 바로 depth = 2에서 필요한 상태이다.

iii) 제약 조건 파악: 상태를 어떻게 활용하는가?

depth = 2의 j번 칸, 즉 (2, j)에 퀸을 놓을 수 있는지 판단(가지치기)하기 위해 앞서 이야기한 상태를 사용한다. 앞선 경우에서라면, 가로 제약은 이미 한 줄에 퀸을 하나씩 두므로 해결하였고, 세로 줄에는 depth = 0일때는 1번칸, depth가 1일때는 3번 칸이 제약에 걸린다. 그리고 대각선의 경우 각각 (0, 1)의 대각선 경로와 (1, 3)의 대각선 경로가 제약에 포함된다.

이를 간단한 규칙을 통해 수식화 해보자. 다음과 같이 4*4 체스판이 있다고 가정하자.

만일, 첫 번째 줄 두 번째 칸 (0,1)에 퀸을 놓는다면 다음과 같이 생각할 수 있다.

당연히 퀸이 들어간 줄과 같은 줄에는 더 이상 퀸이 들어갈 수 없고, 그 아래줄도 마찬가지다. 우선 동일한 행과 열에는 퀸이 들어갈 수 없다. 다음으로, 퀸이 존재하는 부분에 대각선에도 퀸이 들어갈 수 없다. 이를 배열로 나타내보자.

여기에서 규칙을 찾아보자.

우선 퀸이 존재하는 x 혹은 y값이 같다면 같은 행과 열에 존재하므로 그곳에는 퀸을 놓을 수 없다.
- 가로(Row)는 한 줄에 하나씩 퀸을 배치하므로 해결
- 세로(Column)는 이전 퀸의 y 값이 같을때 제약
오른쪽 아래 대각선은 퀸이 존재하는 좌표를 (x, y), 검사할 좌표를 (i, j)라고 했을 때 다음 규칙을 따른다.
- (x - y == i - j)
왼족 아래 대각선은 퀸이 존재하는 좌표를 (x, y), 검사할 좌표를 (i, j)라고 했을 때 다음 규칙을 따른다.
- (x + y == i + j)

즉, 퀸의 위치를 (x, y)라고 하고, 검사할 좌표를 (i, j)라고 했을 때, 앞선 두 개의 식은 다음과 같이 표현할 수 있다.

(x - i) = (y - j)
(x - i) = (j - y)

이를 다음과 같이 정리할 수 있다.

|x - i| == |y - j|

퀸의 x좌표와 검사할 좌표의 x 좌표를 뺀 값과 퀸의 y좌표와 검사할 좌표의 y 좌표를 뺀 값의 절대값이 같다면, 그 값은 대각선에 위치한 값이다.

즉, 제약 조건으로 퀸의 위치가 결정되면, 어디에 새로운 퀸이 놓여지면 안되는지 수식화하여 파악했다.

iv) 그래서 N-Queen의 상태는 무엇인가?

세로 줄 사용 여부
왼쪽 위 - 오른쪽 아래 대각선 사용 여부
오른쪽 위 - 왼쪽 아래 대각선 사용 여부

즉, 여기에서 상태는 depth에서 올바른 다음 선택을 하기 위해, 0부터 depth-1까지의 선택들이 남긴 누적된 기록이다.

2. 종료 조건 설정 - 재귀 호출이 언제 멈춰야 하는가?

재귀 호출 종료는 다음과 같이 볼 수 있다.

성공: 해를 찾은 경우. 여기에서는 N개의 퀸을 모두 배치한 경우.
실패: 더 이상 진행해도 해가 나올 수 없는 경우. 여기에서는 N개의 퀸을 모두 배치할 수 없는 경우.

3. 재귀적 분기 및 가지치기 - 현재 상태에서 시도할 수 있는 모든 다음 선택지 탐색

가지치기: 처음 1번에서 파악한 제약 조건에 위배되는 선택지는 아예 시도조차 하지 않는다.

4. 탐색 및 복구

3번에서 찾은 유효한 선택지들을 하나씩 반복(loop)하면서 다음 과정을 수행한다.

선택(Choose): 하나의 선택지를 고르고, 1번에서 정의한 상태를 변경한다.
탐색(Explore): 변경된 상태로 다음 단계를 재귀 호출한다.
복구(Unchoose/Backtrack): b의 재귀 호출이 성공이든 실패든 끝나고 복귀하면 a에서 변경했던 상태를 정확히 원상 복구 시킨다.
- 원상 복구를 해야, 반목문의 다음 선택지를 "깨끗한" 현재 상태에서 다시 시도할 수 있기 때문이다.

설명만으로는 쉽게 이해하기 어렵다. 그렇다면, 코드를 직접 보면서 각 단계가 어떻게 코드로 적용되는지 하나씩 살펴보자.

I. 이차원 배열 이용

이차원 배열을 이용한 코드의 핵심은, bool 형식의 2차원 판을 이용하여 놓을 수 없는 곳과 놓을 수 있는 곳을 설정하는 것이다.

#include <iostream>
#include <cstring>
#define MAX 15
using namespace std;

int N, cnt = 0;
bool board[MAX][MAX];

// mark: (x, y)에 퀸을 놓으면 공격 가능한 칸을 false로 만든다.
void mark(int x, int y) {
    for (int i = 0; i < N; i++) {
        board[x][i] = false; // 같은 행
        board[i][y] = false; // 같은 열
    }

    for (int i = 0; i < N; i++) {
        int j1 = y - (x - i); // ↙ 대각선
        int j2 = y + (x - i); // ↘ 대각선
        if (j1 >= 0 && j1 < N) board[i][j1] = false;
        if (j2 >= 0 && j2 < N) board[i][j2] = false;
    }

    board[x][y] = true; // 자기 자신은 true 유지
}

void nqueens(int x) {
    if (x == N) {
        cnt++;
        return;
    }

    bool backup[MAX][MAX];
    for (int y = 0; y < N; y++) {
        if (board[x][y]) {
            // 현재 보드 상태 백업
            memcpy(backup, board, sizeof(board));

            // (x, y)에 퀸을 놓고 공격 가능 칸 차단
            mark(x, y);

            nqueens(x + 1);

            // 백업 복원
            memcpy(board, backup, sizeof(board));
        }
    }
}

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

    cin >> N;

    // 모든 칸을 true로 초기화
    memset(board, true, sizeof(board));

    nqueens(0);

    cout << cnt;

    return 0;
}

void mark(int x, int y) {
    for (int i = 0; i < N; i++) {
        board[x][i] = false; // 같은 행
        board[i][y] = false; // 같은 열
    }

    for (int i = 0; i < N; i++) {
        int j1 = y - (x - i); // ↙ 대각선
        int j2 = y + (x - i); // ↘ 대각선
        if (j1 >= 0 && j1 < N) board[i][j1] = false;
        if (j2 >= 0 && j2 < N) board[i][j2] = false;
    }

    board[x][y] = true; // 자기 자신은 true 유지
}

mark 함수는 (x, y)에 퀸을 놓으면 공격 가능한 칸을 false로 만든다.

void nqueens(int x)
{
    if (x == N) {
        cnt++;
        return;
    }

    bool backup[MAX][MAX];
    for (int y = 0; y < N; y++) {
        if (board[x][y]) {
            // 현재 보드 백업
            memcpy(backup, board, sizeof(board));

            // (x, y)에 퀸을 두고 공격 가능한 칸 차단
            mark(x, y, false);

            // 현재 위치만 true로 복원 (자기 자신은 유지해야 함)
            board[x][y] = true;

            nqueens(x + 1);

            // 백업 복원
            memcpy(board, backup, sizeof(board));
        }
    }
}

다음으로 본격적인 재귀 함수인 nqueens를 살펴보자. nqueens는 다음 순서로 작동한다.

만일 x 값이 N(체스 판의 최대 크기)이라면, 모든 칸에 퀸이 적절하게 배치되었으므로, 전체 카운트를 늘려주고 재귀 함수를 종료한다.
현재 칸이, true라면 로직을 수행한다. 만일 true가 아니라면, 놓을 수 없는 칸이므로 가지치기를 통해 연산을 차단한다.
반복문을 통해 현재 행에 대해 0~N까지 퀸을 순서대로 둔다.
현재 보드 상태를 백업하고, (x, y)에 퀸을 두고 공격 가능한 칸을 차단한다.
현재 위치만 true로 복원한다.
- board[x][y] == true라면, 이 칸에는 '퀸을 둘 수 있다'는 의미다. 하지만 (x, y)에는 지금 퀸이 실제로 놓여 있는 상태가 된다. 그런데 만약, (x, y)가 false 상태로 남아 있으면, 다음 재귀 호출(nqueens + 1)이 끝난 뒤 돌아왔을 때 백업 복원 이전까지 이 칸이 '퀸을 두면 안 되는 칸)으로 인식되어 버린다. 즉, 자신이 놓인 위치조차 막힌 자리로 남게 되어 이후 복원 전의 탐색 로직이 꼬이거나, 디버깅 시 상태가 일관되지 않게 된다. 간단하게 말하면 mark(x, y, false)를 통해 공격 가능한 모든 칸을 false로 막는데, 이때 자기 자신도 같이 false로 바꾸어버린다. 하지만 자기 자신은 여전히 퀸이 놓인 유효한 자리이므로 true로 되돌리는 것이다.
다음 행에 대한 재귀 호출을 시작한다.
재귀 호출이 끝나면 백업 해둔 이전 상태로 되돌려 다음 퀸을 두었을때 탐색 로직이 꼬이지 않게 만든다.

로직을 다시 한번 더 정리해보면 다음과 같다.

처음에 2차원 배열을 true로 초기화한다.
각 행에서 가능한 위치에 퀸을 두고, 퀸을 둠으로써 더 이상 퀸을 둘 수 없는 위치를 mark 함수로 false 처리한다.
다음 행으로 이동한다.
만일, 마지막 행에서 퀸을 깔끔하게 두었다면 경우의 수를 1 증가시킨다.
만일, 마지막 행에 도달하지 못하고 퀸을 더 이상 놓을 수 없다면 백트래킹을 통해 다시 탐색한다.

II. 일차원 배열 이용

이번에는 인터넷과 강의에서 쉽게 찾아 볼 수 있는 일차원 배열을 이용한 코드이다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> answer;
int N, cnt = 0;

bool check(int level)
{
	// level은 퀸이 놓인 x 좌표, answer[level]은 퀸이 놓인 y좌표
	// i는 퀸이 놓일 x 좌표, answer[i]는 퀸이 놓일 y좌표
	// answer[level] - level == answer[i] - i
	// answer[level] + level == answer[i] + i
	// |answer[level] - answer[i]| == abs|level - i|
	// 여기에서는 항상 i가 level보다 작으므로 abs 생략
	for (int i = 0; i < level; i++)
		if (answer[i] == answer[level] || abs(answer[level] - answer[i]) == level - i)
			return false;
	return true;
}

void nqueens(int x)
{
	if (x == N) cnt++;
	else
	{
		for (int i = 0; i < N; i++)
		{
			answer[x] = i;
			if (check(x))
				nqueens(x + 1);
		}
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	answer.resize(N+1, 0);

	nqueens(0);

	cout << cnt;

	return 0;
}

코드의 양부터 확연히 차이가 난다. 일차원 배열을 이용한 nqueen 문제의 핵심은, 수학적 계산을 통해 answer에 존재하는, 퀸이 이미 들어가있는 위치를 이용하여 퀸을 놓을 수 있는는 곳인지 검사하고, 놓지 못한다면 백트래킹, 놓을 수 있다면 재귀를 통해 계속 반복한다. 앞서 설명한 내용을 공부했다면 충분히 쉽게 이해할 수 있을 것이다.

시간이 더 오래 걸린것이 두 번째 방법이다.

2차원 배열 + 백업/복원 방식은 각 단계에서 가능한 칸마다 전부 mark()를 호출한다. 그러면 mark는 O(N^2)의 시간 복잡도를 가진다. 그리고 각 호출마다 memcpy 2번도 O(N^2) 시간 복잡도를 가진다. 거기에 깊이가 N인 재귀 트리로, 각 브랜치마다 이런 연산이 반복되어 결론적으로 O(N!) 백트래킹 * O(N^2) 마킹 및 복원 = O(N! * M^2)의 복잡도를 가진다.

반면 두 번째 방법인 1차원 벡터 + 유효성 검사 방식은 answer[level]에 한 행당 한 열만 저장한다. check(level)은 현재 행에서 이전 행들과의 충돌을 검사하는데 최대 O(N)의 시간이 걸린다. 재귀 깊이는 아까와 마찬가지로 N이므로 전체는 O(N! * N)이 된다. 즉, 첫번째 코드보다 약 N배 빨라야한다.

그런데 왜, 백준에서는 실행 시간이 반대로 나왔을까?

여러가지 요인이 있겠지만 아무래도 CPU 입장에서는 bool board[MAX][MAX]는 작은 고정 배열로, 캐시 친화적인, 매우 빠른 접근이 가능한 정도의 크기를 가졌기 때문일 것이다. 반면 두 번째 코드에서는 동적 메모리 구조를(물론 resize로 크기를 고정했지만 내부는 여전히 heap에 있다.)가지고 있으며, 작은 연산이지만 check(level)에서 매번 abs를 호출하고 여러 조건문과 비교하는 과정에서 함수 호출과 분기가 많다. 따라서 메모리 접근이 불연속적이고, 캐시 미스가 상대적으로 많다. 백트래킹 호출 수도 비슷하므로, 함수 호출 오버헤드가 누적될 수 있다. 그러면, 벡터를 배열로 바꿔서 첫번째처럼 사용해보면 결과가 달라질까?

#include <iostream>
#define MAX 15

using namespace std;

int answer[MAX];
int N, cnt = 0;

bool check(int level)
{
	for (int i = 0; i < level; i++)
		if (answer[i] == answer[level] || abs(answer[level] - answer[i]) == level - i)
			return false;
	return true;
}

void nqueens(int x)
{
	if (x == N) cnt++;
	else
	{
		for (int i = 0; i < N; i++)
		{
			answer[x] = i;
			if (check(x))
				nqueens(x + 1);
		}
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	nqueens(0);

	cout << cnt;

	return 0;
}

아쉽게도 그렇지 않다. 분명 시간은 눈에 띄게 단축되었지만, 여전히 속도의 차이는 존재한다. 앞서 말했던 것 처럼, 여기에는 재귀 호출의 차이가 속도의 차이를 나타냈다. 백준에서는 CPU 캐시 친화적인 코드가 유리한 것 같다.

항목	일차원 배열	이차원 배열
이론적 복잡도	낮음 (O(N!))	높음 (O(N! × N²))
가지치기	거의 없음	매우 강함
재귀 호출 수	많음	적음
실험(N ≤ 15) 결과	느림 (3832ms)	빠름 (2132ms)

책을 보고, 여러 영상을 봤다. 이 nqueen 문제도 항상 거의 외워서 풀어버린 문제라 이 참에 제대로 공부해보고 싶어서 도전해 보았는데 생각보다 매우매우 어려웠다. 다만 그럼에도 불구하고, 정리해보니 백트래킹에 조금 더 친숙해진 것 같다.

저작자표시 비영리 변경금지 (새창열림)

'Coding > BaekJoon' 카테고리의 다른 글

[2447] 별 찍기 - 10 (0)	2025.10.20
B_2346 (0)	2023.12.05
B_24511 (0)	2023.12.05
B_13909 (0)	2023.11.27
B_4134 (0)	2023.11.27

초록색이젤다

[9663] N-Queen

문제

입력

출력

예제 입력 1

예제 출력 1

1. 상태 정의 및 제약 조건 파악 - 각 단계(depth)에서 어떤 정보가 유지되어야 하는가?

2. 종료 조건 설정 - 재귀 호출이 언제 멈춰야 하는가?

3. 재귀적 분기 및 가지치기 - 현재 상태에서 시도할 수 있는 모든 다음 선택지 탐색

4. 탐색 및 복구

I. 이차원 배열 이용

II. 일차원 배열 이용

'Coding > BaekJoon' 카테고리의 다른 글

티스토리툴바

[9663] N-Queen

문제

입력

출력

예제 입력 1

예제 출력 1

1. 상태 정의 및 제약 조건 파악 - 각 단계(depth)에서 어떤 정보가 유지되어야 하는가?

2. 종료 조건 설정 - 재귀 호출이 언제 멈춰야 하는가?

3. 재귀적 분기 및 가지치기 - 현재 상태에서 시도할 수 있는 모든 다음 선택지 탐색

4. 탐색 및 복구

I. 이차원 배열 이용

II. 일차원 배열 이용

'Coding > BaekJoon' 카테고리의 다른 글

'Coding/BaekJoon' Related Articles

티스토리툴바