N-Queens

https://leetcode.com/problems/n-queens/description/

N-Queens - LeetCode

 

체스판에 모든 퀸이 서로 공격할 수 없는 위치에 두는 방법을 묻는 문제이다.
퀸은 가로, 세로, 대각선으로 자유롭게 움직일 수 있으므로 해당 위치에 대한 방문 체크를 해주며 백트래킹을 하면 풀 수 있다. 가로, 세로, 대각선을 방문 체크하기 위해서 각 8방향의 배열을 만들어서 while문으로 해당 방향을 체크해주었다. 또한 row의 수는 n 이므로 row마다 퀸이 하나 씩 놓인다는 사실을 알 수 있다. 그러므로 0번 row에서 마지막 row까지 방문 체크를 하며 탐색 할 수 있다면 해당 문제의 조건에 부합하는 경우라는 것을 체크할 수 있다. 아래는 최종적으로 통과한 코드이다.

import java.util.*;  
  
public class Solution {  
  
    final String QUEEN = "Q";  
    final String EMPTY = ".";  
    int[] dr = {0, 1, 0, -1, 1, 1, -1, -1};  
    int[] dc = {1, 0, -1, 0, 1, -1, 1, -1};  
    boolean[][] visited;  
    List<List<String>> answer;  
    int n;  
  
    public List<List<String>> solveNQueens(int n) {  
        this.n = n;  
        answer = new ArrayList<>();  
        visited = new boolean[n][n];  
  
        for(int col = 0; col < n; col++){  
            visited[0][col] = true;  
            dfs(0, col);  
            visited[0][col] = false;  
        }  
  
        return answer;  
    }  
  
    private void dfs(int row, int col){  
        if(invalid(row, col)){  
            return;  
        }  
  
        int nextRow = row + 1;  
  
        if(nextRow == n){  
            List<String> result = new ArrayList<>();  
            StringBuilder resultRow = new StringBuilder();  
            for(int i = 0; i < n; i++){  
                for(int j = 0; j < visited.length; j++){  
                    String value = visited[i][j] ? QUEEN : EMPTY;  
                    resultRow.append(value);  
                }  
                result.add(resultRow.toString());  
                resultRow.setLength(0);  
            }  
  
            answer.add(result);  
            return;  
        }  
  
        for(int nextCol = 0; nextCol < n; nextCol++){  
            if(!visited[nextRow][nextCol]){  
                visited[nextRow][nextCol] = true;  
                dfs(nextRow, nextCol);  
                visited[nextRow][nextCol] = false;  
            }  
        }  
  
    }  
  
    private boolean invalid(int row, int col){  
  
        for(int i = 0; i < dr.length;i ++){  
            int nextRow = row + dr[i];  
            int nextCol = col + dc[i];  
            while(nextRow >= 0 && nextRow < n  
                    && nextCol >= 0 && nextCol < n){  
                if(visited[nextRow][nextCol]) return true;  
                nextRow = nextRow + dr[i];  
                nextCol = nextCol + dc[i];  
            }  
        }  
  
        return false;  
    }  
  
}