알고리즘/programmers

[Programmers] N-Queen

꾸준함. 2022. 6. 14. 00:14

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12952

 

코딩테스트 연습 - N-Queen

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은

programmers.co.kr

n은 최대 12이기 때문에 모든 경우의 수에 대해 가지치기를 하며 진행하면 쉽게 풀 수 있는 문제였습니다.

똑같은 문제로 백준 9663번 N-Queen(https://jaimemin.tistory.com/813)이 있습니다.

 

백준 9663번 N-Queen

문제 링크입니다: https://www.acmicpc.net/problem/9663 전형적인 백트래킹 문제였습니다. 알고리즘은 아래와 같습니다. 1. promising 함수를 통해 해당 칸에 퀸을 배치할 수 있는지 여부를 판단합니다. 2. pro

jaimemin.tistory.com

 

#include <string>
#include <vector>
using namespace std;
const int MAX = 12;
int col[MAX + 1];
int answer;
bool promising(int idx)
{
int k = 1;
bool flag = true;
while (k < idx && flag)
{
if (col[idx] == col[k]
|| abs(col[idx] - col[k]) == idx - k)
{
flag = false;
}
k++;
}
return flag;
}
void queens(int idx, int n)
{
if (promising(idx))
{
if (idx == n)
{
answer++;
}
else
{
for (int i = 1; i <= n; i++)
{
col[idx + 1] = i;
queens(idx + 1, n);
}
}
}
}
int solution(int n) {
queens(0, n);
return answer;
}
view raw .cpp hosted with ❤ by GitHub

 

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~

반응형

'알고리즘 > programmers' 카테고리의 다른 글

[Programmers] 야근 지수  (0) 2022.06.21
[Programmers] 가장 긴 팰린드롬  (0) 2022.06.21
[Programmers] 숫자 블록  (0) 2022.06.14
[Programmers] 멀리 뛰기  (0) 2022.06.14
[Programmers] 거스름돈  (0) 2022.06.14