[C++] Programmers | N-Queen

N-Queen

프로그래머스

---

💡 Backtracking

N-Queen 문제는 백트래킹의 대표적인 예제이다.

풀이에 앞서 백트래킹의 개념에 대해 간단히 알아보자!

 

백트래킹 (Backtracking)

: 백트래킹이란 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하다 원하는 값과 불일치하는 부분이 발생하면
더 이상 탐색을 진행하지 않고 전 단계로 돌아가는, 이름 그대로 방금 왔던 길을 되짚어가는 알고리즘이다. 

 

✍🏻 풀이

 

N-Queen

해당 문제의 조건을 만족시키기 위해서는

1) 한 행

2) 한 열

3) 한 대각선

에 단 하나의 퀸만을 배치해야 한다.

 

첫 번째 조건인 '한 행에 단 하나의 퀸만을 배치할 수 있다'는 조건을 만족시키기 위하여 일차원 배열을 사용했다.

(예를들어 chess[1]에 3이라는 값이 들어있으면, 1행 3열에 퀸이 배치되어 있다는 뜻이다.)

 

두 번째 조건인 '한 열에 단 하나의 퀸만을 배치할 수 있다'는 조건을 만족시키기 위하여 isValid 함수에서 chess 배열의 원소 값 중 해당 값과 겹치는 값이 있다면 false를 반환하도록 하였다.

 

세 번째 조건인 '한 대각선에 단 하나의 퀸만을 배치할 수 있다'는 조건을 만족시키기 위하여 isValid 함수에서 chess 배열의 원소 값 중 행의 차이와 열의 차이가 같은 원소가 있다면 false를 반환하도록 하였다.

---

✅ Accept Code

// programmers week5-5
// N-Queen
// Backtracking

#include <bits/stdc++.h>

using namespace std;

int chess[12];
int answer = 0;

bool isValid(int depth) {
    for (int i = 0; i < depth; i++) {
        if (chess[depth] == chess[i] || abs(chess[depth] - chess[i]) == depth - i) return false;
    }
    return true;
}

void DFS(int n, int depth) {
    if (depth == n) {
        answer++;
        return;
    }
    for (int i = 0; i < n; i++) {
        chess[depth] = i;   // queen 배치
        if (isValid(depth)) DFS(n, depth + 1);
    }
}

int solution(int n) {
    DFS(n, 0);
    return answer;
}

---

Reference

[Python] 백트래킹 (+ DFS와 차이)

 

[백준 / BOJ] - 9663번 N-Queen C++ 풀이

---

백트래킹만 나오면 지레 겁을 먹는 경향이 있는데, 다른 분들의 코드를 참고하며 이해하니 아주 간단하게 느껴졌다.

백준에서 백트래킹 관련 문제들을 많이 찾아서 풀어봐야겠다 🤓