문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

문제 해결

문제해결1

나의 문제해결방식은 아래와 같다.

• 2차원 배열(board)에 board의 층[0]부터 q를 하나 지정한다.
• 층[1]부터는 q의 왼쪽대각선, 위, 오른쪽대각선에 q가 있나 확인하고, 놓는다. 만약 놓을 수 없다면 다시 이전 층으로 돌아간다. ([1]에서 놓을 곳이 없다면 [0]으로 돌아간다.)
• 돌아갔을때 q를 오른쪽으로 한칸 옮기고 다시 아래층으로 내려간다.
• 층이 board의 길이와 같게되면 q가 모두 위치한것이므로 answer++를 한다.

코드

class Solution {
    static int answer = 0;
    
    // 대각선 왼쪽 검사
    static boolean diagonalLeft(int l, int i, int[][]board) {
        int x = l - 1, y = i - 1;
        
        while(x >= 0) {
            if (y < 0) break;
            if (board[x--][y--] == 1) return false;
        }
        return true;        
    }
    
    // 대각선 오른쪽 검사
    static boolean diagonalRight (int l, int i, int[][] board) {
        int x = l - 1, y = i + 1;
        
        while (x >= 0) {
            if (y >= board.length) break;
            if (board[x--][y++] == 1) return false;
        }        
        return true;
    }
    
    // 위쪽 검사
    static boolean up (int l, int i, int[][] board) {
        int x = l - 1, y = i;
        
        while (x >= 0) {
            if (board[x--][y] == 1) return false;
        }
        return true;
    }
    
    static void dfs(int l, int[][] board) {
        if (l == board.length) answer++;                                
        else {
            for (int i = 0; i < board.length; i++) {
                if ((l == 0) || diagonalLeft(l, i, board) && diagonalRight(l, i, board) && up(l, i, board)) {
                    board[l][i] = 1;
                    dfs(l+1, board);
                    board[l][i] = 0;
                }
            }
        }
    }
    
    public int solution(int n) {        
        int[][] board = new int[n][n];                        
        dfs(0, board);        
        return answer;
    }
}

이렇게 풀어도 되지만 일차원 배열을 활용하여 더욱 간단하게 해결할수도 있다.

---

문제해결2

다음은 일차원 배열만으로도 해결할 수 있는 방법이다.
일차원 배열의 index가 column에 해당하고, index안의 값이 row에 해당한다.
예를들어 board = {1, 2, 3, 4}라면 1은 board[0][1]에 q가 있다는 뜻이다.

그 다음은 이차원배열과 비슷하다.
board[row]의 값을 바꿔보면서 조건에 통과되면 dfs의 다음층으로 넘어가고, 그렇지 않으면 다음층으로 가지 않으면된다.

• board[row]에 값을 정해주기
• board[row]이전의 값들 (board[row-1], board[row-2]...)이 위, 대각선 양방향에 없는지 확인하기 (check)
• check가 통과되면 다음층(row + 1)으로 가기

check

• board[row]의 위의 방향에 q가 있는지 확인하기
  board[row]와 board[row-1], board[row-2]... board[0]까지 같은수가 없는지 확인하면 된다.
• board[row]의 양 대각선 방향에 q가 있는지 확인하기
  기울기를 이용하면된다.
  예를들어 board[1][1]과 board[2][2]의 기울기가 같다면 대각선 방향에 있는것이다.
  board[x1][y1], board[x2][y2]라고 할때 |x1-x2| 와 |y1 - y2|이 값이 같으면 기울기가 같은 것이다.

즉 위의 두 조건을 만족하면 true를 반환한다.

코드

import java.util.*;

class Solution {     
    static int[] board;
    static int answer = 0;
                
    public int solution(int n) { 
        board = new int[n];
        dfs(0);
        
        return answer;
    }              
    
    static void dfs (int row) {
        if (row == board.length) answer++;                    
        else {
            for (int i = 0; i < board.length; i++) {
                board[row] = i;
                
                if (check(row)) dfs(row+1);                
            }
        }
    }
    
    static boolean check (int row) {
        for (int i = 0; i < row; i++) {
            if (board[i] == board[row]) return false;
            if (Math.abs(i - row) == Math.abs(board[i] - board[row])) return false;
        }
        
        return true;
    }
}