[프로그래머스] N-Queen

N-Queen

 

 

코드 구현

import java.util.*;
class Solution {
    int cnt=0;
    public int solution(int n) {
        //가로 세로 같은 줄에 있음 안되고,
        //대각선에 겹침 안됨..
        //퀸 놓을 때마다 카운트, 말==n이면 카운트
        //조건 뚫고 n개 다 놓을 수 있는 경우의 수를 구하기
        //부모row != 자식row
        //부모col != 자식col
        //[row+1][col-1] || [row+1][col+1] => 대각선
        //혹은 Math.abs(line[i]-col)==Math.abs(i-row) 여기서 i는 변하는 row값
        int[] line=new int[n];//행 별로 열을 기록하자.
        dfs(line,0,n);
        return cnt;
    }
    public void dfs(int[] line,int row,int n){
        if(row==n){
            cnt++;
            return;
        }
        for(int i=0;i<n;i++){//col순회
            if(isValid(line,row,i)){
                line[row]=i;//되는열
                dfs(line,row+1,n);//재귀 시도
                line[row]=0;//성공이면 cnt증가했을 거고 실패면 그냥 돌아왔을텐데 일단 다른col도 순회해보기위해 turn전에 초기화한다.(*핵심)-돌아오는 과정. - 한 행별로 열 여러개 순회해야하므로 순열 개념임.
            }
        }
    }
    public boolean isValid(int[] line,int row,int col){//이 행에 이 col값 놔도 돼요?, 다른 행에 col겹치면 안되니 행 돌며 col자리 비었는지 체크합니다
        for(int i=0;i<row;i++){//row까지 순회(지금까지) => 다른 행에 영향받을만한거있는지 행별 조회
            if(line[i]==col || Math.abs(line[i]-col) == Math.abs(i-row)){
                //열끼리 차이==행끼리 차이면,대각선 관계. 특) row는 바뀌는값
                return false;
            }
        }
        return true;
    }
}

 

 

 

---

 

 

 

 

풀고나니, 꽤 재미있는 포인트가 많은 문제라고 느꼈다.

보통은 한칸씩 체크하는데, 최소 거리를 구하면서도 & 해당 행,열, 대각선에도 존재하면 안된다는 

체스의 기본 규칙을 떠올리며 센스를 발휘해 풀어야 하는 문제.

 

이 녀석 풀고 싶어서 풀고, 또 풀고, 이해하고 반복했다.

물어보니 주변의 친구들도 이 문제를 많이 어려워하고 아직도 이해를 못한 사람도 봐서

그래도 이해하고 풀이에 성공한 스스로가 자랑스러웠음..😅

자세한 풀이는 주석문을 참고하자!