[프로그래머스] - N-Queen(C/C++)

프로그래머스

[문제 설명]

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

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

 

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

제한사항

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

---

입출력 예

 

n	result
4	2

---

[문제 풀이]

문제를 풀때 어딘가 익숙한 문제였다..

알고보니 백준에 동일한 문제가 있었고.. 풀었던 문제였다.

하지만.. 풀었던 기억만 날뿐 코드는 생각나지 않았다.

 

처음 접근했던 방법은 vector<pair<int,int>>를 사용하여 queen의 위치를 다 저장하는 방법을 사용했다.

가로축과 세로축 모두 탐색해야한다고 생각했기에 2중 배열을 통해 2중 반복문을 돌렸다.

코드 작성을 끝내고 제출했는데 마지막 테스트케이스에서 시간초과가 났다.

실제로 입력으로 입력 최대값인 12를 넣었더니 어마어마한 시간이 걸렸다.

 

다른 방법을 생각해봤다.

퀸이 이동할 수 있는 위치는 가로, 세로, 대각이다.

퀸이 놓인 행에는 다른 퀸은 절대 놓을 수가 없다.

 

따라서 이차원 배열로 저장할 필요 없이 vector<int>의 각 인덱스를 행으로, 인덱스의 값을 열로 생각할수가 있다.

퀸을 위에서부터 놓는다고 가정하고, 각 열에 놓는 경우만 고려하면 되기에 반복문 한개를 포함한 재귀를 통해서 문제를 풀수가 있다.

 

우선 퀸을 놓을수 있는지 체크하기 위해서 함수를 하나 작성했다.

현재 놓을 행의 윗부분을 반복문을 통해 아래의 조건을 체크해준다.

1. rows[cur] == rows[i] , 현재 퀸을 놓은 열과 위에 행들에서 퀸이 놓은 열이 같은지 체크, 즉 세로 부분에 퀸이 위치해있는지 체크한다. 가로는 체크하지 않아도 되는 이유는 퀸을 놓을수 있다면 놓고 바로 다음행으로 넘어갈 것이기 때문이다.

 

2. abs(rows[cur] - rows[i]) == abs(cur - i), 옆에 식은 대각선을 검사하는 조건이다.

현재 위치 cur에서 대각선에 위치해있다는것은 좌표로 생각했을때 임의의 숫자 n에 대해서

왼쪽 위 대각선은 (cur_y - n, cur_x - n)

왼쪽 아래 대각선은 (cur_y + n, cur_x - n)

오른쪽 위 대각선은 (cur_y - n, cur_x + n)

오른쪽 아래 대각선은 (cur_y + n, cur_x + n)

이다.

 

체크하는 방법은 현재 위치의 cur_x, cur_y 검사할 대상의 x2, y2를 각각 뺏을때 동일한 절댓값이 나온다면 대각선에 위치한다고 할 수 있다.

abs(cur_x - x2) == abs(cur_y - y2) 은 위의 식 abs(rows[cur] - rows[i]) == abs(cur - i)와 같다.

 

위의 과정을 통해 퀸을 놓을 수 있는 위치인지 체크한다.

놓을수 있다면 놓고, 재귀를 통해 다음행을 바로 검사한다.

행은 재귀를 통해 알아서 넘어가고, 반복문을 통해 바뀌는 부분은 열 부분이다.

행이 입력받은 n과 동일해진다면 answer의 값을 증가시킨다.

 

이렇게 모든 반복문과 재귀가 종료되면 answer를 리턴하면 된다.

 

[코드]

[GitHub]

GitHub - EGyeom/ProblemSolving

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

#include <string>
#include <vector>

using namespace std;

vector<int> rows(12,0);
int answer;

bool isPossible(int y)
{
    for(int i = 0; i < y; i++)
    {
        if((rows[y] == rows[i]) || (abs(rows[y] - rows[i]) == abs(y - i)))
            return false;
    }

    return true;
}

void dfs(int num, int n)
{
    if(num == n)
    {
        answer++;
        return;
    }
    for(int i =0; i < n; i++)
    {
        rows[num] = i;
        if(isPossible(num))
            dfs(num+1, n);
    }
}

int solution(int n) {
    dfs(0, n);
    return answer;
}