[프로그래머스] N-Queen

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

n이 12이하의 자연수 이므로 완전탐색으로 해결할 수 있다. 백트래킹을 사용한 완전탐색을 통해 해결했다. 모든 경우를 시도해서 가능한 경우를 카운트해주면 된다.

코드

C++

#include <string>
#include <vector>
using namespace std;

int N, ans;
vector<vector<bool>> map;

bool check(int x, int y) {
    // 세로 검사
    for (int i = 0; i < N; i++) {
        if (i == y) continue;
        if (map[i][x]) return false;
    }

    // 가로 검사
    for (int j = 0; j < N; j++) {
        if (j == x) continue;
        if (map[y][j]) return false;
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == y && j == x) continue;
            // 기울기가 양수인 대각선 검사
            if (i + j == x + y && map[i][j]) return false;
            // 기울기가 음수인 대각선 검사
            if (j - i == x - y && map[i][j]) return false;
        }
    }
    return true;
}

void dfs(int y) {
    if (y == N) {
        ans++;
        return;
    }

    for (int i = 0; i < N; i++) {
        map[y][i] = true;
        if (check(i, y)) dfs(y + 1);
        map[y][i] = false;
    }
}

int solution(int n) {
    N = n;
    map = vector<vector<bool>>(n, vector<bool>(n));
    dfs(0);
    int answer = ans;
    return answer;
}

Java

class Solution {
    int N;
    int ans = 0;
    boolean[][] map;

    boolean check(int x, int y) {
        // 세로 검사
        for (int i = 0; i < N; i++) {
            if (i == y) continue;
            if (map[i][x]) return false;
        }
        // 가로 검사
        for (int j = 0; j < N; j++) {
            if (j == x) continue;
            if (map[y][j]) return false;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(i == y && j == x) continue;
                // 기울기가 양수인 대각선 검사
                if (i + j == x + y && map[i][j]) return false;
                // 기울기가 음수인 대각선 검사
                if (j - i == x - y && map[i][j]) return false;
            }
        }
        return true;
    }

    public void dfs(int y, int cnt) {
        if (y == N) {
            ans++;
            return;
        }

        for (int j = 0; j < N; j++) {
            map[y][j] = true;
            if (check(j, y)) dfs(y + 1, cnt+1);
            map[y][j] = false;
        }
    }

    public int solution(int n) {
        N = n;
        int answer = 0;
        map = new boolean[n][n];
        dfs(0, 0);
        answer = ans;
        return answer;
    }
}