Programmers - Lv3 N-Queen
규칙 찾기
- Queen은 상하좌우 및 모든 방향의 직선 대각선을 이동할 수 있다.
1. 상, 하 | 좌, 우
- 매우 쉽게 찾을 수 있는 규칙으로 Queen이 특정 위치에 존재할 때 같은 행, 같은 열에는 Queen이 존재할 수 없다.
2. Positive Diagonal
- 대각선으로 이동할 수 있을 때 좌상, 우하 방향으로 이동하는 것을 Positive 방향이라고 가정하자.
- 각 행, 열에 대해 다음과 같은 규칙을 찾을 수 있다.
- 만약 우하 방향으로 이동한다면, 열은 +1 | 행은 +1 되기에(좌상 방향도 부호는 바뀌지만 마찬가지) 뺄셈은 항상 같을 수밖에 없다.
- 따라서 (행 - 열) 사칙연산을 수행하면 이동 가능한 모든 Positive 대각선에서 모두 같은 값이 나온다.
3. Negative Diagonal
- 대각선으로 이동할 수 있을 때 좌하, 우상 방향으로 이동하는 것을 Negative 방향이라고 가정하자.
- 마찬가지로 다음과 같은 규칙을 찾을 수 있다.
- 우상 방향으로 이동한다면, 열은 + 1 | 행은 -1 되기에 둘의 덧셈은 항상 같을 수밖에 없다.
- 따라서, (행 + 열)의 값은 Negative 방향의 대각선의 이동 경로에서 모두 같다.
문제 풀이
위 3가지 규칙을 사용해서 문제를 풀 수 있다.
- 우선 같은 행에는 Queen이 존재할 수 없으므로 행은 검사하지 않고 Queen을 놓는 순간 다음 행으로 넘어가는 방식으로 계산하면 연산을 줄일 수 있다.
- 첫 번째 행에 대해서만 Queen을 하나씩 배치해 보고 나올 수 있는 모든 상황의 갯수가 정답이다. 첫 번째 행에 모두 배치한 이후 다음 행으로 넘어가면 중복되는 결과가 나온다.
for (let i = 0; i < n; i++) {
// 각 index마다 Q을 배치했다고 가정하고 연산 후 넘어간다.
// 이는 첫 번째 행에 대한 배치이다.
}
- 확인해야 될 조건은 3가지
(상하 | Positive | negative)
이므로 각각을 Set 객체를 통해 값을 저장해놓고, Set.prototype.has()
메서드를 통해 Queen을 놓을 수 있는지 없는지 검사한다.
for (let i = 0; i < n; i++) {
const col = new Set();
const pos = new Set();
const neg = new Set();
col.add(i);
pos.add(0 - i);
neg.add(0 + i);
}
- 첫 번째 행이 아닌 두 번째 행부터 Queen을 배치할 때 가능한 상황이 다음과 같이 두 개 이상일 수 있다. 따라서, 반복문이 아닌 DFS를 이용해서 Brute Force 방식으로 순회하도록 작성했다.
const dfs = (r, n, col, pos, neg) => {
if (r === n) {
// 모든 행을 검사했을 때 처리
} else {
// DFS의 파라미터로 행(r)을 전달해주고, 열(c)은 for 문으로 순회하면서 확인한다.
for (let c = 0; c < n; c++) {
// 만약 상하, pos, neg 방향에 Queen이 존재하면 다음 열로 넘어간다.
if (col.has(c) || pos.has(r - c) || neg.has(r + c)) {
continue;
}
// 겹치지 않으면 해당 위치에서의 상하, pos, neg 포지션을 Set 객체에 추가하고,
// 다음 행으로 넘어간다.(재귀 호출한다.)
col.add(c);
pos.add(r - c);
neg.add(r + c);
dfs(r + 1, n, col, pos, neg);
// DFS를 재귀 호출한 후 다음 행을 확인하기 위해 다시 delete 해준다.
col.delete(c);
pos.delete(r - c);
neg.delete(r + c);
}
}
};
작성 완료된 코드
const solution = (n) => {
let answer = 0;
const dfs = (r, n, col, pos, neg) => {
if (r === n) {
answer += 1;
} else {
for (let c = 0; c < n; c++) {
if (col.has(c) || pos.has(r - c) || neg.has(r + c)) {
continue;
}
col.add(c);
pos.add(r - c);
neg.add(r + c);
dfs(r + 1, n, col, pos, neg);
col.delete(c);
pos.delete(r - c);
neg.delete(r + c);
}
}
};
for (let i = 0; i < n; i++) {
const col = new Set();
const pos = new Set();
const neg = new Set();
col.add(i);
pos.add(0 - i);
neg.add(0 + i);
dfs(1, n, col, pos, neg);
}
return answer;
};
Author And Source
이 문제에 관하여(Programmers - Lv3 N-Queen), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@apparatus1/Programmers-Lv3-N-Queen
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
위 3가지 규칙을 사용해서 문제를 풀 수 있다.
- 우선 같은 행에는 Queen이 존재할 수 없으므로 행은 검사하지 않고 Queen을 놓는 순간 다음 행으로 넘어가는 방식으로 계산하면 연산을 줄일 수 있다.
- 첫 번째 행에 대해서만 Queen을 하나씩 배치해 보고 나올 수 있는 모든 상황의 갯수가 정답이다. 첫 번째 행에 모두 배치한 이후 다음 행으로 넘어가면 중복되는 결과가 나온다.
for (let i = 0; i < n; i++) {
// 각 index마다 Q을 배치했다고 가정하고 연산 후 넘어간다.
// 이는 첫 번째 행에 대한 배치이다.
}
- 확인해야 될 조건은 3가지
(상하 | Positive | negative)
이므로 각각을 Set 객체를 통해 값을 저장해놓고,Set.prototype.has()
메서드를 통해 Queen을 놓을 수 있는지 없는지 검사한다.
for (let i = 0; i < n; i++) {
const col = new Set();
const pos = new Set();
const neg = new Set();
col.add(i);
pos.add(0 - i);
neg.add(0 + i);
}
- 첫 번째 행이 아닌 두 번째 행부터 Queen을 배치할 때 가능한 상황이 다음과 같이 두 개 이상일 수 있다. 따라서, 반복문이 아닌 DFS를 이용해서 Brute Force 방식으로 순회하도록 작성했다.
const dfs = (r, n, col, pos, neg) => {
if (r === n) {
// 모든 행을 검사했을 때 처리
} else {
// DFS의 파라미터로 행(r)을 전달해주고, 열(c)은 for 문으로 순회하면서 확인한다.
for (let c = 0; c < n; c++) {
// 만약 상하, pos, neg 방향에 Queen이 존재하면 다음 열로 넘어간다.
if (col.has(c) || pos.has(r - c) || neg.has(r + c)) {
continue;
}
// 겹치지 않으면 해당 위치에서의 상하, pos, neg 포지션을 Set 객체에 추가하고,
// 다음 행으로 넘어간다.(재귀 호출한다.)
col.add(c);
pos.add(r - c);
neg.add(r + c);
dfs(r + 1, n, col, pos, neg);
// DFS를 재귀 호출한 후 다음 행을 확인하기 위해 다시 delete 해준다.
col.delete(c);
pos.delete(r - c);
neg.delete(r + c);
}
}
};
작성 완료된 코드
const solution = (n) => {
let answer = 0;
const dfs = (r, n, col, pos, neg) => {
if (r === n) {
answer += 1;
} else {
for (let c = 0; c < n; c++) {
if (col.has(c) || pos.has(r - c) || neg.has(r + c)) {
continue;
}
col.add(c);
pos.add(r - c);
neg.add(r + c);
dfs(r + 1, n, col, pos, neg);
col.delete(c);
pos.delete(r - c);
neg.delete(r + c);
}
}
};
for (let i = 0; i < n; i++) {
const col = new Set();
const pos = new Set();
const neg = new Set();
col.add(i);
pos.add(0 - i);
neg.add(0 + i);
dfs(1, n, col, pos, neg);
}
return answer;
};
Author And Source
이 문제에 관하여(Programmers - Lv3 N-Queen), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@apparatus1/Programmers-Lv3-N-Queen
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
const solution = (n) => {
let answer = 0;
const dfs = (r, n, col, pos, neg) => {
if (r === n) {
answer += 1;
} else {
for (let c = 0; c < n; c++) {
if (col.has(c) || pos.has(r - c) || neg.has(r + c)) {
continue;
}
col.add(c);
pos.add(r - c);
neg.add(r + c);
dfs(r + 1, n, col, pos, neg);
col.delete(c);
pos.delete(r - c);
neg.delete(r + c);
}
}
};
for (let i = 0; i < n; i++) {
const col = new Set();
const pos = new Set();
const neg = new Set();
col.add(i);
pos.add(0 - i);
neg.add(0 + i);
dfs(1, n, col, pos, neg);
}
return answer;
};
Author And Source
이 문제에 관하여(Programmers - Lv3 N-Queen), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@apparatus1/Programmers-Lv3-N-Queen저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)