프로그래머스[Lv.2] - N-Queen

 

문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

https://school.programmers.co.kr/learn/courses/30/lessons/12952

---

 

 

 

 

 

 

제한 사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

---

 

 

 

 

 

 

풀이

N-Queen은 매우 유명한 문제이다.

한 번씩 풀이를 보고 이해했지만 막상 풀라고 하면 못 푸는 경우가 많다.

 

우선, N-Queen을 풀기 위해서는 Queen의 이동방식을 이해해야 한다.

Queen은 상하좌우를 이동할 수 있으며 대각선(↗, ↘) 모두 이동가능하다.

이 Queen들이 서로 공격할 수 없게 배치하는 경우의 수를 세는 문제이다.

 

Queen들이 서로 공격할 수 없게 하기 위해서는 같은 행, 같은 열에 위치해서는 안되며 대각선에도 위치해서는 안 된다.

그렇다면 같은 행에 있지 않더라도 같은 열에 위치한다면 조건을 만족할 수 없으니 열과 행은 하나로 간주하여 진행해도 문제가 없다.

즉, 임의의 행에 Queen을 위치했다고 하면 열에 대한 조건은 만족했다고 가정하는 것이다.

 

이제 대각선에 대한 체크만 하면 된다.

대각선은 ↗, ↘ 두 가지 종류가 있다.

우선 ↗의 경우를 보자.

Queen이 같은 ↗대각선에 위치하기 위해서는 행과 열의 인덱스를 더한 값이 같으면 된다.

즉, x+y가 같으면 같은 대각선이다.

예를 들어, {1, 0}과 {0, 1}은 같은 대각선에 위치한다.

 

↘ 의 경우는 행과 열의 인덱스 차이가 같은 것들끼리 같은 대각선에 위치한다.

즉, x-y+n-1이 같으면 같은 대각선이다.

n-1을 더해주는 이유는 인덱스가 음수로 가는 것을 막기 위해서이다.

예를 들어, {1, 0}과 {2, 1}은 같은 대각선에 위치한다.

 

0	1	2	3
0	1	2	3
0	1	2	3
0	1	2	3

col 행, 열

0	1	2	3
1	2	3	4
2	3	4	5
3	4	5	6

↗ 대각선

3	4	5	6
2	3	4	5
1	2	3	4
0	1	2	3

↘대각선

 

이를 이용하여 백트래킹을 통해 가능 여부를 판단하면 된다.

0행 0열부터 시작하여 Queen을 위치시켰다 가정하며 진행하고 불가능한 위치에는 Queen을 놓지 않는다.

즉, 재귀를 진행하지 않는다.

그러다 마지막 행에 Queen을 위치시킬 수 있다면 가능한 경우가 된 것이다.

---

 

 

 

 

 

전체 코드

#include <string>
#include <iostream>
#include <vector>

using namespace std;

int cnt = 0;

void search(int n, int y, vector<int>& col, vector<int>& diag1, vector<int>& diag2)
{
    if(y == n)
    {
        cnt++;
        return;
    }
    
    for(int x = 0; x < n; x++)
    {
        if(col[x] || diag1[x+y] || diag2[x-y+n-1]) continue;
        
        col[x] = diag1[x+y] = diag2[x-y+n-1] = 1;
        search(n, y+1, col, diag1, diag2);
        col[x] = diag1[x+y] = diag2[x-y+n-1] = 0;
    }
}

int solution(int n) {
    int answer = 0;
    
    vector<int> col(n, 0);
    vector<int> diag1(2*n, 0);
    vector<int> diag2(2*n, 0);
    
    search(n, 0, col, diag1, diag2);
    
    return cnt;
}

---