[3단계] 2. N-Queen
아래 모든 문제들은 프로그래머스에서 제공 되는 문제를 이용하였습니다, 감사합니다.
- 틀린거 없음!
N-Queen
문제 설명
가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.
예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.
체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.
제한사항
- 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
- n은 12이하의 자연수 입니다.
입출력 예
가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.
예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.
체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.
풀이
#include <string>
#include <vector>
#include <iostream>
#include <array>
using namespace std;
void point_check(vector<vector<int>> &table, int n, int col, int row, int value)
{
int i =0;
for(; col < n; col++)
{
table[row][col] += value;
if(row - i >= 0)
table[row - i][col] += value;
if(row + i < n)
table[row + i][col] += value;
i++;
}
}
void dfs(vector<vector<int>> &table, int n, int col, int row, int &answer)
{
if (n == col)
{
answer++;
return;
}
for(row = 0; row < n; row++)
{
if(table[row][col] == 0)
{
point_check(table,n,col,row,1);
dfs(table, n, col + 1, row, answer);
point_check(table,n,col,row,-1);
}
}
}
int solution(int n) {
int answer = 0;
vector<vector<int>> table(n,vector<int>(n,0));
dfs(table, n, 0, 0, answer);
return answer;
}
설명
- q를 놓을 수 있는 위치를 정해 판별해야한다.
- 왼쪽 부터 q를 놓아보고, q를 놓은 자리에서 오른쪽 대각선 직선 들에 못놓는다고 기록을 남겨두었다.
- dfs의 for에서 같은 열에 행을 바꿔가며, 퀸을 놓아본다.
- 만약 해당 row, col자리의 값이 0이라면 놓아도 되는 자리이므로,
- 해당 자리에 q을 놓는데, 그 자리에 놓게되면 다음 퀸을 놓을때 못놓는 자리가 생기므로, 못놓는다는걸 배열에 표시해주고, col+1을 해주어 다음 열의 q은 어느 위치에 놓을지 선택해주게 로직을 구상하였다.
Author And Source
이 문제에 관하여([3단계] 2. N-Queen), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hey-chocopie/3단계-2.-N-Queen저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)