Algorithm/Programmers
programmers_N-Queen_java
owoowo
2023. 5. 19. 19:39
728x90
https://school.programmers.co.kr/learn/courses/30/lessons/12952
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
두 점 사이 기울기 == 1 -> (x1 - x2) == (y1 - y2) -> 대각선 상에 위치
class Solution {
private static int count;
public static int solution(int n) {
int answer = 0;
count = 0;
dfs(n, 0, new int[n]);
answer = count;
return answer;
}
public static void dfs(int n, int col, int[] visited){
if(col == n){
count++;
return;
}
for (int i = 0; i<n; i++){
visited[col] = i;
if (isPossible(col, visited)){
dfs(n, col+1, visited);
}
}
}
public static boolean isPossible(int col, int[] visited){
for (int i = 0; i< col; i++){
if (visited[col] == visited[i]){ // 같은 열에 퀸이 배치되어 있는 경우
return false;
}
if (Math.abs(col-i) == Math.abs(visited[col] - visited[i])){ // 대각선상 퀸이 배치되어 있는 경우(두 점 사이 기울기== 1)
return false;
}
}
return true;
}
}