[프로그래머스] N-queen

문제 주소

https://school.programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스

문제 설명

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

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

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

제한사항

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

---

입출력 예

n result

4

2

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

제출 코드

import java.util.*;

class Solution {
    
    int count;
    int limit;
    int [] arr;
    
    public int solution(int n) {
        
        ArrayList<Integer> list = new ArrayList<>();
        boolean [] visit = new boolean[n];
        arr= new int[n];
        limit = n;
        add(0);
        
        return count;
    }
    
    public void add(int depth){

        if(limit<=depth){
            count++;
            return;
        }
        
        boolean [] visit = new boolean [limit];
        
        for(int i=0;i<depth;i++){
            
            int element = arr[i];
            visit[element]=true;
            //좌대각선 체크
            int diff = depth -i;
            int left =  element - diff;
            if(left>=0){
                visit[left] = true;
            }
            //우대각선 체크
            int right = element + diff;
            if(right<limit){
                visit[right]=true;
            }
        }
        
        for(int i=0;i<limit;i++){
            if(visit[i]){
                continue;
            }
            arr[depth] = i;
            add(depth+1);
        }
    }
}

테스트 1 〉	통과 (0.03ms, 79.4MB)
테스트 2 〉	통과 (0.02ms, 65.8MB)
테스트 3 〉	통과 (0.02ms, 74.8MB)
테스트 4 〉	통과 (0.06ms, 76.1MB)
테스트 5 〉	통과 (0.15ms, 73.5MB)
테스트 6 〉	통과 (0.35ms, 86.5MB)
테스트 7 〉	통과 (0.94ms, 83.1MB)
테스트 8 〉	통과 (2.18ms, 89.8MB)
테스트 9 〉	통과 (7.02ms, 73.2MB)
테스트 10 〉	통과 (28.37ms, 82.2MB)
테스트 11 〉	통과 (218.28ms, 110MB)

코드 해설

백트래킹 문제임

체스에서 퀸은 대각선 상하좌우로 다 움직이니까 한 퀸을 기준으로 8방향으로 뻗어나가는 선에 다른 퀸이 맞으면 안됨

-> 한 row에는 원소가 하나만 있을 수 있음

그래서 row를 index라고 치고 그 안에서의 퀸의 위치를 element로 저장함

 

원소 하나를 넣고 visit도 2차원 배열로 만들려다가 굳이 다 체크할 필요가 없고 내가 퀸을 추가할 row에서만 따져주면 되니까

이미 들어있는 원소의 대각선빔이나 아래쪽으로 쏘는 빔에 해당되는 자리를 visit[i] = true로 체크해준 후 

빔에 맞지 않는 자리에만 퀸을 추가해서 dfs로 재귀를 돌렸다

dfs라서 원소 하나 붙이고 그 원소에다가 n개가 될때까지 이어서 붙이기에 배열이 하나만 필요하다!

 

원소가 n개가 되면 count를 증가시키도록 함

 

메모리 아끼려고 노력했는데 2차원 visit이 있으면 실행시간은 대폭 단축될 거 같긴 하다

 

 

풀이과정

처음에는 백트래킹 문제라고 생각하고 ArrayList 를 만들어서 풀었는데 풀고나니까 count만 세면 되는 데다가 dfs인데 굳이 ArrayList를 달고다닐 필요가 없어서 배열로 바꿈

import java.util.*;

class Solution {
    
    int count;
    
    public int solution(int n) {
        
        ArrayList<Integer> list = new ArrayList<>();
        boolean [] visit = new boolean[n];
        add(n,list);
        
        return count;
    }
    
    public void add(int limit, ArrayList<Integer> list){

        if(limit==list.size()){
            count++;
            return;
        }
        
        boolean [] visit = new boolean [limit];
        
        for(int i=0;i<list.size();i++){
            
            int element = list.get(i);
            visit[element]=true;
            int left =  element - (list.size()-i);
            if(left>=0){
                visit[left] = true;
            }
            int right = element + (list.size()-i);
            if(right<limit){
                visit[right]=true;
            }
        }
        
        for(int i=0;i<limit;i++){
            if(visit[i]){
                continue;
            }
            
            ArrayList<Integer> newList = new ArrayList<>(list);
            newList.add(i);
            add(limit,newList);
        }
    }
}

처음에 풀었던 방식

테스트 1 〉	통과 (0.03ms, 70.1MB)
테스트 2 〉	통과 (0.05ms, 75.3MB)
테스트 3 〉	통과 (0.04ms, 76.1MB)
테스트 4 〉	통과 (0.18ms, 77.4MB)
테스트 5 〉	통과 (0.81ms, 68.8MB)
테스트 6 〉	통과 (1.51ms, 74.4MB)
테스트 7 〉	통과 (2.71ms, 78.5MB)
테스트 8 〉	통과 (6.91ms, 78.4MB)
테스트 9 〉	통과 (13.55ms, 80.5MB)
테스트 10 〉	통과 (64.29ms, 107MB)
테스트 11 〉	통과 (136.98ms, 143MB)