문제 링크

문제 간단 해석

가로, 세로, 대각선을 살펴봤을 때 겹치는 체스말이 없는지 확인하는 문제.

Java

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을 호출.

Python

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 함수를 통해 해당 위치의 세로, 대각선들에 값을 기입하여 재귀함수 동작 시 체스말을 놓지 못하도록 한다.
하나의 재귀가 끝나면, 현재 위치, 세로, 대각선들에 대한 값들을 다시 빼준다.