[알고리즘] 프로그래머스 N-Queen -연습문제- -백트랙킹-

https://programmers.co.kr/learn/courses/30/lessons/12952?language=kotlin

코딩테스트 연습 - N-Queen

 

 

 

프로그래멋 LEVEL3 의 백트래킹 유형의 N-Queen 문제를 풀어봤습니다.

예전에 백준에서도 풀었었는데 아마 백트랙킹의 대표적인 문제라 프로그래머스에도 있는 것 같습니다.

복습할겸 다시한번 풀어봤습니다 ㅎㅎ

 

풀이는 다음과 같습니다. 

[Java]

class Solution {
    public static int N;
    public static int answer = 0;

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(8);
    }
    public static void dfs(int[] map, int row) {
        if (row == N) { //마지막행까지 다 놓은 경우
            answer++;
        } else {
            for (int col = 1; col <= N; col++) {
                map[row + 1] = col;
                if (check(map, row + 1)) {
                    // 놓을 수 있는 자리인 경우 다음행으로 재귀
                    dfs(map, row+1);
                }
            }
        }
    }

    public 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;
    }

    public int solution(int n) {
        N = n;
        for (int i = 1; i <= n; i++) {
            int[] map = new int[n + 1];
            map[1] = i;
            dfs(map, 1);
        }
        return answer;
    }
}

 

 

[Kotlin]

internal class Solution {

    fun solution(n: Int): Int {
        N = n
        for (i in 1..n) {
            val map = IntArray(n + 1)
            map[1] = i
            dfs(map, 1)
        }
        return answer
    }

    companion object {
        var N: Int = 0
        var answer = 0

        @JvmStatic
        fun main(args: Array<String>) {
            val solution = Solution()
            solution.solution(8)
        }

        fun dfs(map: IntArray, row: Int) {
            if (row == N) { //마지막행까지 다 놓은 경우
                answer++
            } else {
                for (col in 1..N) {
                    map[row + 1] = col
                    if (check(map, row + 1)) {
                        // 놓을 수 있는 자리인 경우 다음행으로 재귀
                        dfs(map, row + 1)
                    }
                }
            }
        }

        fun check(map: IntArray, row: Int): Boolean {
            for (i in 1 until row) { // 이전 행들 반복문
                // 이전행의 같은 열에 체스가 있었는지
                if (map[i] == map[row]) {
                    return false
                }
                //대각선 공격 가능한지
                if (Math.abs(i - row) == Math.abs(map[i] - map[row])) {
                    return false
                }
            }
            return true
        }
    }
}

 

 

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