문제 링크입니다: 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
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |

개발환경: 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 |