[알고리즘] 백준 9663 N-Queen -백트랙킹- 자바 코틀린

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

9663번: N-Queen

 

 

 

[2020-04-02]

원래 row을 행 col을 열로 알고 있었는데 갑자기 햇갈려서 구글검색해서 풀었을 당시 밑처럼 나와서 row가 열이였다는 충격을 받고 row를 열이라 표현하고 풀었었네요... 밑은 잘못된거고 row는 행 col이 열 맞습니다. ㅎㅎㅎ

문제풀이에서 row col이 의미가 바뀌게 풀었으니 유의바랍니다.

[2020-05-08]

col, row 바껴있던거 코드 수정했습니다!

 

 

백트랙킹의 대표적인 예시라고 불리는 N-Quuen 문제를 풀어봤습니다.

 

[문제]

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

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

 

처음에 문제를 잘못 이해해서 N x N 의 체스판에서 퀸을 놓을 수 있는 총 경우의 수로 실수했습니다.

문제를 잘 보고 풀어야겠습니다.

 

1. 첫번째 행으로 스타트를 합니다. (첫번째 행의 열을 차례대로 반복문을 돌립니다.)

2. 같은 행에는 한개의 퀸 밖에 못 두므로 끝 행까지 놓았다면 다 놓은거므로 result++ 

3. 일차원 배열로 풀 경우 'map[행] = 열' 로 풀었습니다.

4. dfs() 는 현재 행에서 퀸을 성공적으로 놓았을 경우 다음 행을 검사하기 위해 호출합니다. 두번째 매개변수인 col은 퀸이 놓여져 있는 행을 전달합니다.

5. dfs() 에서는 마지막 행까지 성공적으로 놓은 경우 result를 증가시켜주며 아닌 경우는 해당 행의 열을 차례대로 검사하며 놓을 수 있다면 다음 행으로 dfs() 재귀를 돌립니다.

6. check() 함수는 해당 행열에 퀸을 놓을 수 있는지 체크해주는 함수입니다. 첫번째로 해당 열에 퀸이 놓아져있는지 체크합니다. 두번째로 대각선을 검사합니다. (이 대각선 검사하는 수식을 알고 있어야합니다. => 현재좌표의 행과열을 뺸 절대값과 비교좌표의 행과열을 뺸 절대값이 같으면 서로 대각선에 있는 좌표입니다.)

 

 

 

 

코드는 다음과 같습니다.

import java.util.Scanner;

class Main {
    static int result = 0;
    static int N;

    /*
     *  int map[행인덱스(row)] = 열인덱스(col)
     * */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        // 첫번째 행 1...N열 차례대로 퀸 놓고 다음 행 호출
        for (int col = 1; col <= N; col++) {
            int[] map = new int[N + 1];
            map[1] = col;
            dfs(map, 1);
        }
        System.out.println(result);
    }

    static void dfs(int[] map, int row) {
        if (row == N) { // 마지막 행까지 탐색 완료
            result++;
        } else { // 해당 행의 열을 처음 부터 N 까지 차례대로 탐색
            for (int col = 1; col <= N; col++) {
                map[row + 1] = col;
                if (check(map, row + 1)) {
                    // 놓을 수 있는 경우 다음 행 재귀
                    dfs(map, row + 1);
                }
            }
        }
    }

    // 퀸 놓을 수 있는 자린지 체크하는 함수
    static boolean check(int[] map, int row) {
        // 현재 퀸을 놓을려는 행의 이전 행들 차례대로 검사
        for (int i = 1; i < row; i++) {
            // 이전 행들에 같은 열에 퀸이 있는 경우
            if (map[i] == map[row]) {
                return false;
            }
            // 이전 행들에 대각선 공격 가능한 퀸이 있는 경우
            if (Math.abs(i - row) == Math.abs(map[i] - map[row])) {
                return false;
            }
        }
        return true;
    }
}

 

 

 

 

 

[2020-09-30 복습]

 

[Java]

import java.util.Scanner;

public class Main {
    static int n;
    static int result = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            int[] num = new int[n + 1];
            num[1] = i;
            dfs(num, 1);
        }
        System.out.println(result);
    }

    static void dfs(int[] num, int row) {
        if (row == n) {
            result++;
            return;
        }
        for (int j = 1; j <= n; j++) {
            num[row + 1] = j;
            if (check(num, row + 1)) {
                dfs(num, row + 1);
            }
        }
    }

    static boolean check(int[] num, int row) {
        for (int i = 1; i < row; i++) {
            if (num[i] == num[row]) { //같은열존재
                return false;
            }
            if (Math.abs(i - row) == Math.abs(num[i] - num[row])) { //대각선존재
                return false;
            }
        }
        return true;
    }
}

 

 

[kotlin] 

import java.util.*

internal var n: Int = 0
internal var result = 0

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    n = sc.nextInt()
    for (i in 1..n) {
        val num = IntArray(n + 1)
        num[1] = i
        dfs(num, 1)
    }
    println(result)
}

internal fun dfs(num: IntArray, row: Int) {
    if (row == n) {
        result++
        return
    }
    for (j in 1..n) {
        num[row + 1] = j
        if (check(num, row + 1)) {
            dfs(num, row + 1)
        }
    }
}

internal fun check(num: IntArray, row: Int): Boolean {
    for (i in 1 until row) {
        if (num[i] == num[row]) { //같은열존재
            return false
        }
        if (Math.abs(i - row) == Math.abs(num[i] - num[row])) { //대각선존재
            return false
        }
    }
    return true
}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!