[C++로 풀이] N-Queen (백트래킹)⭐⭐⭐

📌 N-Queen

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이 ⭕

#include <string>
#include <vector>

using namespace std;

void DFS(vector<vector<bool>> queen, int& answer, int row)
{
    if (row == queen.size()) {
        answer++;            
        return;
    }

    for (int col = 0; col < queen[row].size(); ++col) { // 1️⃣ 첫번째 행당 하나만 들어갈 수 잇음
        bool isOk = true;
        for (int i = row - 1, j = 1; i >= 0; --i, ++j) { // 2️⃣3️⃣4️⃣ 를 검사하자. (이전 행들에서 검사)
            bool con1 = queen[i][col]; // 2️⃣같은 열에 놓여진 퀸이 있는지
            bool con2 = col - j >= 0 && queen[i][col - j]; // 3️⃣ 왼쪽 대각선에 놓여진 퀸이 있는지
            bool con3 = col + j <= queen.size() - 1 && queen[i][col + j]; // 4️⃣ 오른쪽 대각선에 놓여진 퀸이 있는지
            if (con1 || con2 || con3) { // 셋 중 하나라도 해당 된다면 이 queen[row][col] 자리에 퀸을 놓을 수 없다.
                isOk = false;
                break;
            }
        }
        if (isOk) { // 0 ~ row-1 행들을 모두 검사했어도 위 검사를 통과했다면 queen[row][col]은 놓여질 수 있다! 
            queen[row][col] = true; // 퀸 놓기
            DFS(queen, answer, row + 1); // 다음 행 검사하러 
            queen[row][col] = false; // 퀸 지우기. 
        }
    }
}

int solution(int n) {
    int answer = 0;
    vector<vector<bool>> queen(n, vector<bool>(n, false));
    DFS(queen, answer, 0);
    return answer;
}

성공 👉 n 줄의 퀸을 다 채웠다면 BACK 하기

실패 👉 현재의 행의 이전 행들에서 1️⃣같은 행 2️⃣같은 열 3️⃣왼쪽 대각선 4️⃣오른쪽 대각선 에 이미 퀸이 놓여져 있다면 해당 자리에 퀸을 놓을 수 없으므로 BACK 하기

• queen에 퀸을 놓기로 결정한 자리를 방문 체크한다.
• DFS
  • 재귀 단계 👉 “행”단위
  • 각 단계마다(= 즉, 행마다) 모든 열들에 차례대로 퀸을 놓아보고 놓을 수 있는지 검사
• “1️⃣ 같은 행” 조건의 경우 어차피 for문을 통해 해당 “열”에서 하나씩 차례대로 지정해보므로 이 for문만으로도 첫번째 조건은 이미 만족이다.

        if (isOk) { // 0 ~ row-1 행들을 모두 검사했어도 위 검사를 통과했다면 queen[row][col]은 놓여질 수 있다! 
            queen[row][col] = true; // 퀸 놓기
            DFS(queen, answer, row + 1); // 다음 행 검사하러 
            queen[row][col] = false; // 퀸 지우기. 
        }

• 방문 체크 해제 (퀸 지우기)
  • n줄 채우기를 실패하든 성공하든 일단 돌아왔다면 다음 for문의 DFS (다음 열을 선택한것에서 뻗어나가는 DFS) 에서 이전 행들에서 2️⃣3️⃣4️⃣ 검사할 때 퀸이 놓여져 있는 걸로 체크되면 안되기 때문에. 실패했든 성공했든 지워주어야 함.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기