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

2024. 11. 14. 17:27·🐸 Problem Solving/BOJ

 

🔗 문제 링크 : https://www.acmicpc.net/problem/9663

 


 

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

 

 

 

 

입출력 예시

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

 

 

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

 

 

입출력 예시

 

 

 


 

풀이 

여덟 퀸 문제를 일반화한 퍼즐 문제인, N-Queen 문제이다.

백트래킹 기법으로 해결하는 게 일반적이므로 백트래킹을 익히는데 도움이 된다.

 

  • Queen 은 상하, 좌우, 대각선까지 공격이 가능한 말이다.
    • 위 특징(특히 좌우 공격)을 이용하여, 첫 번째 퀸은 체스판의 첫 번째 줄, 두 번째 퀸은 체스판의 두 번째 줄에 배치하는 식으로 문제를 해결할 수 있다.
  • 아래 풀이는 N개의 퀸을 배치하기 위해 PlaceQueen()을 재귀호출 하게 된다.
    • 0번째부터 N-1번째 퀸의 배치를 위해 PlaceQueen(0)을 시작으로 PlaceQueen(N-1)까지 호출한다.
    • PlaceQueen(N)을 호출한 경우, 문제의 조건을 모두 충족시킨 퀸의 배치가 완료된 것이므로, count를 1 증가시킨다.
  • 다음 퀸의 배치를 위한 재귀호출 직전에는, 현재 선택한 퀸의 배치로 영향을 주는 칸(isUsed[])을 기억해서 다음 퀸의 배치를 결정한다.

 

🧩 isUsed의 쓰임

  • `isUsed0 배열`은 상하, 즉 '해당 열이 다른 퀸으로부터 영향을 받는가?'에 대한 정보를 담고 있다.
  • 예를 들어, `isUsed0[1]`이 `true`인 경우, 체스판의 1열은 다른 퀸의 영향을 받는 열이라는 것을 알 수 있다.
  • 그림으로 보면 아래와 같다.

isUsed0

 

 

 

  • `isUsed1 배열`은 '해당 좌하-우상 대각선이 다른 퀸으로부터 영향을 받는가?'에 대한 정보를 담고 있다.
    • N x N의 체스판에서는 대각선이 2N - 1개 존재한다.
  • 예를 들어, `isUsed1[0]`과 `isUsed1[3]`이 `true`인 경우, 아래 그림처럼 해당 대각선은 다른 퀸의 영향을 받는 자리임을 알 수 있다. 

isUsed1

 

 

 

  • `isUsed2 배열`은 '해당 좌상-우하 대각선이 다른 퀸으로부터 영향을 받는가?'에 대한 정보를 담고 있다.
  • 예를 들어, `isUsed2[0]`, `isUsed2[3]`, `isUsed2[4]`가 `true`인 경우, 아래 그림처럼 해당 대각선은 다른 퀸의 영향을 받는 자리임을 알 수 있다.

isUsed2

 

 

전체 풀이는 아래와 같다.

#include <iostream>
using namespace std;

bool isUsed0[20];    // 상하
bool isUsed1[20];    // 대각선 (좌하-우상) x+y
bool isUsed2[20];    // 대각선 (좌상-우하) x-y
int N;
int count = 0;

void PlaceQueen(int n) {
    /* 퀸을 N개 모두 배치한 경우 */
    if (n == N) {
        count++;
        return;
    }

    for (int i = 0; i < N; i++) {
        /* 퀸끼리 서로 공격이 가능한 자리인 경우 */
        if (isUsed0[i] || isUsed1[n + i] || isUsed2[n - i + N - 1]) continue;
        
        isUsed0[i] = true;
        isUsed1[n + i] = true;  
        isUsed2[n - i + N - 1] = true; 
        PlaceQueen(n + 1);
        isUsed0[i] = false;
        isUsed1[n + i] = false;  
        isUsed2[n - i + N - 1] = false; 
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin >> N;
    PlaceQueen(0);
    cout << count;
}

 

 

 


저작자표시 비영리 변경금지 (새창열림)

'🐸 Problem Solving > BOJ' 카테고리의 다른 글

[BOJ/C++] 백준 2178번: 미로 탐색  (0) 2024.11.20
[BOJ/C++] 백준 1753번: 최단경로  (0) 2024.11.08
[BOJ/C++] 백준 10828번: 스택  (0) 2024.11.07
'🐸 Problem Solving/BOJ' 카테고리의 다른 글
  • [BOJ/C++] 백준 1920번: 수 찾기
  • [BOJ/C++] 백준 2178번: 미로 탐색
  • [BOJ/C++] 백준 1753번: 최단경로
  • [BOJ/C++] 백준 10828번: 스택
Mojing_
Mojing_
매일 매일 경험치를 쌓는 모징이의 개발 블로그입니다 :) This is Mojing’s Dev Blog where she gain experience points every day. :)
  • Mojing_
    모징이의 개발 경험치
    Mojing_
  • 전체
    오늘
    어제
    • 분류 전체보기 (142)
      • 👻 Unity (3)
        • 🔧 기능 구현 (0)
        • 💡 유니티 팁 (0)
        • 📘 Unity 노트 (1)
        • 🏗️ 디자인 패턴 (0)
        • 🎨 그래픽 & 렌더링 (0)
      • 💻 Programming (14)
        • C (3)
        • C++ (9)
        • C# (0)
        • Swift (2)
      • 💾 Computer Science (16)
        • Algorithm (9)
        • Software Engineering (7)
      • 🐸 Problem Solving (108)
        • Programmers (41)
        • BOJ (67)
      • 🔋 ETC (0)
      • 💡 Quest Log (0)
  • 인기 글

  • 공지사항

  • 태그

    dynamic programming
    DFS/BFS
    C++
    programmers
    티스토리챌린지
    Design Pattern
    BOJ
    sort
    CS
    backtracking
    오블완
    탐색
    프로그래머스
    Problem Solving
    algorithm
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
Mojing_
[BOJ/C++] 백준 9663번: N-Queen
상단으로

티스토리툴바