백준 9663 N-Queen Kotlin,c (백트래킹)

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

9663번: N-Queen

문제

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

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

입력

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

출력

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

풀이

행렬 그래프에서의 백트래킹 알고리즘을 공부할 때 기본이 되는 문제이다.

기본적으로 dfs 알고리즘이 사용되는데, dfs는 가능한 모든 경로를 탐색하기 때문에, 목표지점이 있는 경로가 아닌 경로 탐색에 시간을 잡아먹는다.

이에 백트래킹은 dfs에 조건을 줘서 가지치기를 통해 탐색할 필요가 없는 경로는 탐색하지 않아, 가지치기를 얼마나 잘 하느냐에 따라 효율성이 극대화된다.

 

우선 퀸의 이동 반경은 퀸과 같은 행과 열이고, 대각선이다.

N*N 크기의 체스 판이 주어질 때, N개의 퀸을 서로 공격할 수 없는 자리에 배치하는 경우의 수를 구해야 한다.

 

board[row] = i

1차원 배열의 board에 현재 행(row)의 i열에 퀸을 둔다.

그 이후 백트래킹으로 현재 행에 퀸을 둘 자리를 탐색하는데, 이는 재귀를 통한 dfs로 구현 가능하다.

만약 현재 행의 i열에 퀸을 두고, 현재 행의 i열에 퀸을 둘 수 있다면 (이전 행들에 놓여진 퀸과 동일한 행과열, 대각의 자리가 아니라면) dfs(row+1)로 다음 행에 퀸을 둘 수 있는지 탐색해 나가고, 현재 행의 i열에 퀸을 둘 수 없다면

다음 행이 아닌 현재 행의 i+1열에 퀸을 둘 수 있는지 탐색한다. 

 

코드(Kotlin)

import kotlin.math.*

var answer=0

fun isPossible(row : Int,board : IntArray) : Boolean{

    for(i in 0 until row){
    //현재 둘 퀸의 자리가 이전까지 퀸들의 행과열,대각선 자리라면 둘 수 없음
        if(board[i]==board[row] || (row-i == abs(board[row]-board[i])))
            return false
    }
    return true
}

fun dfs(row : Int,board : IntArray,n : Int){

	//한 행씩 퀸을 두면서 내려왔으므로, 현재 행이 n과 같아진다면 n개의 퀸을 두었다는 의미
    if(row == n){
        answer++
        return
    }
    for(i in 0 until n ){
        board[row] = i
        //현재 행의 열에 퀸을 둘 수 있으면 다음 행 이어서 탐색
        //현재 행의 열에 퀸을 둘 수 없다면 현재 행의 다음 열 이어서 탐색
        if(isPossible(row,board)){
            dfs(row+1,board,n)
        }
    }

}

fun main() = with(System.out.bufferedWriter()){
    //1<=n<=15
    val br =System.`in`.bufferedReader()
    val n = Integer.parseInt(br.readLine())
    val board = IntArray(n)
    dfs(0,board,n)
    write("$answer")
    close()
}

코드(c)

#include <stdlib.h>
#include <stdio.h>

int answer = 0;
bool check(int *graph, int row) {
	for (int i = row-1; i >= 0; i--) {
		//위의 행들이 세로로 있거나 대각에 있으면 return false
		if (graph[i] == graph[row]) {
			return false;
		}
		if (abs(graph[row] - graph[i]) == abs(row - i)) {
			return false;
		}
	}
	return true;
}


void backTracking(int *graph,int row, int n) {

	if (row == n) {
		answer++;
		return;
	}
	
	//체스판의 각 행마다 모두 퀸을 놓아보고, 되면 다음 행, 안 되면 다음 열
	for (int col = 0; col < n; col++) {
		graph[row] = col;
		if (check(graph, row)) {
			backTracking(graph, row + 1, n);
		}
		graph[row] = 0;
	}
	
}

int main() {

	int n;
	scanf("%d", &n);

	//동적 배열
	int *graph = (int*)malloc(sizeof(int) * n);

	for (int i = 0; i < n; i++) {
		graph[i] = 0;
	}
	backTracking(graph,0, n);
	printf("%d", answer);
	return 0;
}