백준 9663번: N-Queen

문제

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

9663번: N-Queen

 

---

풀이

N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 구하는 문제입니다.

체스 규칙에 따르면 퀸은 상하좌우, 대각선 방향으로 기물이 없는 칸에 한해서 칸수의 제한 없이 움직일 수 있는 말입니다. 따라서 퀸은 xy 좌표로 생각했을 때 각 x 좌표에 1개씩, 각 y 좌표에 1개씩 있어야 하고 대각선상에서 겹치면 안 됩니다.

---

코드

C언어

정수 배열 x와 nQueen 함수의 매개변수 y는 각각 n x n 크기의 체스판에서의 x 좌표와 y 좌표를 의미합니다. 정수 배열 board는 퀸의 위치(board[y 좌표] = x 좌표)를 기록하는 역할을 합니다.

함수 안의 for문에서 xy 좌표를 (i, y)로 표현하고 x 좌표가 i인 곳에 퀸이 위치하고 있지 않다면(x[i] != 1) board[y] = i로 현재 y값에 대한 퀸의 위치를, x[i] = 1으로 x 좌표가 i인 곳에 퀸을 1개 두었다는 것을 기록합니다.

이후에 대각선상에 퀸이 있는지 확인하기 위해 j를 포함한 for문으로 2개의 퀸의 x 좌표의 차이와 y 좌표의 차이가 같은지 확인합니다. 이때 j가 0이면 board[y] - board[y - 0] = 0이기 때문에 항상 if문을 만족하기 때문에 j는 1부터 시작합니다.

위의 모든 조건을 만족하면 체스판에서 다음 y 값에 대해 검사하기 위해 재귀적으로 nQueen(y + 1)을 실행하고 모든 y 값에 퀸을 1개씩 놓았다면(y == n) 이 문제의 조건을 만족하는 것이므로 cnt에 1을 더해줍니다.

y 좌표가 0일때부터 n - 1일 때까지 확인하기 위해 main 함수에서 nQueen(0)을 실행한 뒤에 cnt를 출력합니다.

#include <stdio.h>
#include <math.h>
int n, board[15], x[15] = { 0 }, cnt = 0;
void nQueen(int y) {
	if (y == n) {
		cnt++;
		return;
	}
	for (int i = 0; i < n; i++) {
		if (x[i] != 1) {
			board[y] = i;
			x[i] = 1;
			int tst = 1;
			for (int j = 1; j <= y; j++) {
				if (abs(board[y] - board[y - j]) == j) {
					tst = 0;
					break;
				}
			}
			if (tst) nQueen(y + 1);
			x[i] = 0;
		}
	}
}
main() {
	scanf("%d", &n);
	nQueen(0);
	printf("%d", cnt);
}

자바

사실 이 문제는 백트래킹 카테고리에 위치해있긴 하지만 dfs(깊이우선탐색)을 이용하여 푸는 문제라고도 할 수 있습니다. 이를 표현하기 위해 위의 C언어 코드에서 nQueen 함수 이름을 dfs로, 함수의 매개변수 y를 dpth로, 정수 배열 x를 bool 배열 visited로 바꿔보았습니다. 풀이는 위와 같습니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    static int n, cnt = 0;
    static int[] arr;
    static boolean[] visited;

    public static void dfs(int dpth) {
        if (dpth == n) {
            cnt++;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                arr[dpth] = i;
                visited[i] = true;
                boolean tst = true;
                for (int j = 1; j <= dpth; j++) {
                    if (Math.abs(arr[dpth] - arr[dpth - j]) == j) {
                        tst = false;
                        break;
                    }
                }
                if (tst) {
                    dfs(dpth + 1);
                }
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        visited = new boolean[n];
        dfs(0);
        System.out.println(cnt);
    }
}

 

---

결론

처음에 이 문제를 풀 때는 dfs이라는 알고리즘을 알고있지 않은 상태였습니다. 추후에 자바를 공부하기 시작하면서 dfs에 대해 알게 되었는데 이 알고리즘을 모르는 상태에서도 비슷한 방식으로 풀었다는 사실에 놀랐던 기억이 있습니다. 앞으로도 알고리즘을 모른다고 문제를 포기하는 것이 아니라 끝까지 노력하여 풀 수 있는 사람이 되기 위해 노력해야겠습니다.