가로, 세로, 대각선을 살펴봤을 때 겹치는 체스말이 없는지 확인하는 문제.
1차원 배열로 해결.
class Solution {
private int[] place;
private int n;
private int answer = 0;
public void check(int step) {
if (step == n) {
answer++;
return;
}
val: for (int v = 0; v < n; v++) {
for (int i = 0; i < step; i++) {
if ((v == place[i]) || (step - i == Math.abs(v - place[i])))
continue val;
}
place[step] = v;
check(step + 1);
}
}
public int solution(int n) {
place = new int[n];
this.n = n;
check(0);
return answer;
}
}
public void check(int step) {
if (step == n) {
answer++;
return;
}
val: for (int v = 0; v < n; v++) {
for (int i = 0; i < step; i++) {
if ((v == place[i]) || (step - i == Math.abs(v - place[i])))
continue val;
}
place[step] = v;
check(step + 1);
}
}
0부터 n까지, 이번 step에 들어갈 값을 결정
내 위의 체스말들과 비교한다.
세로가 겹치거나(v == place[i]
),
대각선이 겹치면(step - i == Math.abs(v - place[i]
)
v를 다시 결정한다.
겹치지 않는다면 해당 위치에 v를 넣고, 다음 step을 호출.
2차원 배열로 해결.
def solution(n):
answer = 0
field = [[0] * n for _ in range(n)]
dx = [-1, 0, 1]
def area(r, c, TF):
adder = 1 if TF else -1
for to in range(3):
m = 1
while True:
y = r + m
x = c + m * dx[to]
if 0 <= y < n and 0 <= x < n:
field[y][x] += adder
m += 1
else:
break
def queen(r=0):
if r == n:
nonlocal answer
answer += 1
return
for c in range(n):
if not field[r][c]:
field[r][c] += 1
area(r, c, True)
queen(r + 1)
field[r][c] -= 1
area(r, c, False)
queen()
return answer
dx = [-1, 0, 1]
def area(r, c, TF):
adder = 1 if TF else -1
for to in range(3):
m = 1
while True:
y = r + m
x = c + m * dx[to]
if 0 <= y < n and 0 <= x < n:
field[y][x] += adder
m += 1
else:
break
전달받은 r, c 위치에 대해 y와 x를 구한다. 좌측 대각선, 세로, 우측 대각선 순이다.
해당 위치들에 접근하여 값을 추가하거나 감소시킨다.
if r == n:
nonlocal answer
answer += 1
return
for c in range(n):
if not field[r][c]:
field[r][c] += 1
area(r, c, True)
queen(r + 1)
field[r][c] -= 1
area(r, c, False)
r과 c로 배열을 확인, 값이 0이라면 해당 위치에 1 표시 및 area 함수를 통해 해당 위치의 세로, 대각선들에 값을 기입하여 재귀함수 동작 시 체스말을 놓지 못하도록 한다.
하나의 재귀가 끝나면, 현재 위치, 세로, 대각선들에 대한 값들을 다시 빼준다.