[프로그래머스](Java) - N-Queen

문제링크

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

문제풀이

대표적인 백트랙킹 문제로 이전에 다른 사람의 소스를 보면서 풀었었는데 지금은 혼자서 고민하고 다시 구현해 볼 수 있었다.

기존의 dfs와 비슷하지만 방문했던 숫자인지 체크하는 boolean [] chk를 대개 사용했는데 여기서는 가로, 세로, 대각선으로 같은 칸에 겹치면 안되므로 이 세조건에 대한 체크를 chk 함수를 통해서 진행했다.

0번째 행에 무조건 하나가 있어야 하므로 0번째 행의 각 칸에서 처음 dfs를 시작시킨다.
현재 dfs가 가지고 있는 체스말의 위치를 arraylist를 통해서 저장하고 있는데
arraylist의 idx가 행, idx의 값이 열이 되어 체스말의 위치가 map[i][list.get(i)]의 형태로 저장된다.
dfs를 진행시킬떄마다 이 arraylist에 새로운 값들이 저장되고, dfs를 나올때 그 값을 제거해준다.

list.add(i);
dfs(i,idx+1,list);
list.remove(list.size()-1);

list에는 현재 체스말의 위치들이 담겨있으므로
현재의 체스말 map[y][x]가 다른 체스말들과 가로, 세로, 대각선으로 겹치지 않는지 확인하며
체스말에 대해 각각 체크해줘야하므로 arraylist의 크기만큼 for문을 돌린다.

    public static boolean chk(int y, int x, ArrayList<Integer>list){
        int len = list.size();
        //이미 놓여진 점은 map[i][list.get(i)] 놓일 점 map[y][x]
        for(int i=0; i<len; i++){
            //세로        //가로            //대각
            if(y==i || x==list.get(i) || (int)(Math.abs(y-i))==(int)(Math.abs(x-list.get(i)))){
                return false;
            }            
        }
        return true;
    }

코드

import java.util.*;

class Solution {
    
    static int nn;
    static int [][] map;
    static boolean []checker;
    static int answer;
    
    
    public int solution(int n) {
        
        nn = n;
        map = new int[n][n];
        checker = new boolean[n];
        ArrayList<Integer> list = new ArrayList();
        
        for(int i=0; i<n; i++){
            checker[i]= true;
            list.add(i);
            dfs(i,1,list);
            list.remove(list.size()-1);
            Arrays.fill(checker,false);
        }
        
        return answer;
    }
    
    public static void dfs(int n, int idx, ArrayList<Integer>list){
        
        if(idx==nn){
            answer++;
            return;
        }
        
        for(int i=0; i<nn; i++){

            if(!chk(idx,i,list)){
                continue;
            }
            
            list.add(i);
            dfs(i,idx+1,list);
            list.remove(list.size()-1);

        }
 
    }
    
    public static boolean chk(int y, int x, ArrayList<Integer>list){
        int len = list.size();

        //이미 놓여진 점은 map[i][list.get(i)] 놓일 점 map[y][x]
        for(int i=0; i<len; i++){
            
            //세로        //가로            //대각
            if(y==i || x==list.get(i) || (int)(Math.abs(y-i))==(int)(Math.abs(x-list.get(i)))){

                return false;
            }            
        }

        return true;
        
    }
}