[c++][백준 9663][BFS] N-Queen - 컴도리돌이

---

 

9663번: N-Queen

---

풀이 과정

- 퀸은 가로, 세로, 대각선으로 나아갈 수 있는 말이다. 즉, 퀸 하나를 놓으면, 그 퀸과 같은 가로, 세로, 대각선에는 또 다른 퀸을 놓을 수 없다.

- 해당 문제는 dfs의 재귀 호출로 해결하였으며, 2차원 배열과 1차원 배열 두 가지로 해결을 하였다. 1차원 배열을 사용하는 게 미숙하여 다른 블로거님들의 풀이를 보면서 이해하면 문제를 풀었고 혼자 풀 때는 1차원 배열을 풀어야겠다는 생각을 못하여 2차원 배열로 해결하였다.

- 0번째 행부터 각 행에 대해 각각 1~n까지의 칸에 퀸이 있는 모든 경우를 탐색하였다. 탐색 중 해당 칸에 퀸을 놓는 것이 허용되면 놓고 그렇지 않으면 반환해준다. 해당 r이 n에 다다르면 퀸을 다 규칙에 맞게 놓았기에 answer 값을 카운트해준다.

 

1. 풀이 1

#include<iostream>
#include<vector>

using namespace std;

int n;
int answer = 0;

vector<int> row;

bool check(int r)
{
    for(int i=0; i< r; i++)
    {
        if(row[i] == row[r] or abs(row[r] - row[i]) == r - i) return false;
    }
    return true;
}

void nqueen(int r)
{
    if(r == n)
    {
        answer ++;
        return;
    }

    for(int i=0; i<n; i++)
    {
        row[r] = i;
        if(check(r))
        {
            nqueen(r+1);
        }
    }

}

void input()
{
    cin >> n;
    row.resize(n,0);
}

void solution()
{
    input();
    nqueen(0);
    cout << answer ;
}

int main(void)
{
    solution();
}

 

2. 풀이 2

#include<iostream>
#include<vector>

using namespace std;

bool queen(vector<vector<bool>>& visited,int x,int y)
{
    int xx,yy;
    xx = x-1;
    yy = y;
    while(xx >= 0)
    {
        if(visited[xx][yy]) return false;
        xx --;
    }
    xx = x - 1;
    yy = y - 1;
    while(xx >=0 and yy >=0)
    {
        if(visited[xx][yy]) return false;
        xx --;
        yy --;
    }
    xx = x - 1;
    yy = y + 1;
    while(xx >=0 and yy < visited.size())
    {
        if(visited[xx][yy]) return false;
        xx --;
        yy ++;
    }
    return true;
}

void dfs(vector<vector<bool>>& visited,int x,int& answer)
{
    if(x == visited.size())
    {
        answer++;
        return;
    }
    for(int i=0; i<visited.size(); i++)
    {
        visited[x][i] = true;
        if(queen(visited,x,i)) dfs(visited,x+1,answer);
        visited[x][i] = false;
    }
}

int main(void)
{
    int n,answer =0;
    cin >> n;
    vector<vector<bool>> visited(n,vector<bool>(n,false));

    dfs(visited,0,answer);
    cout << answer ;
}