[BOJ/백준] 9663 N-Queen

● [문제번호 9663] N-Queen

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

 

● 알아야 할 것

: DFS

: 백트레킹

: 브루트 포스 (Brute Force)

 

 

● 풀이 과정

: 이렇게 저렇게 구현하다가 '시간 초과'에서 못 벗어나서 구글링을 하였다.

 

: 방문기록을 2차원으로 구현하니까 서로 공격하는 퀸의 발견에서 시간 소요가 되었다.

그래서 구글링해보니 1차원 배열로 가능하고 오히려 더 수월하게 구현할 수 있게 만드는 게 가능했다.

 

1차원 배열 → 2차원 배열 (의미 해석)

 

: DFS 풀이과정

1. 현재 index의 값에 row값을 저장

 

2. 현재index까지 중에서 서로 공격하는 퀸이 없다면

2-1. 행에 있는 지 확인

2-2. 대각선 (좌상단~우하단) 에 있는 지 확인

→ X좌표끼리 차이 == Y좌표끼리 차이

2-3. 대각선 (좌하단~우상단) 에 있는 지 확인

→ x1+ y1 == x2 + y2

 

3. 없다면 다음 index로 재귀

3-1. 있다면 다시 1번으로

 

 

● 주의 할 것

: NULL

 

 

● 참고 할 것

: 풀이과정 참고

https://cryptosalamander.tistory.com/58

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// chess[col] : index → col / 값 → row
// 그러면 자연스럽게 같은 열에 퀸이 놓일 수 없음
int chess[16];
int N, sol;

// 서로 공격하는 퀸이 있는 지 확인
bool check(int col)
{
    // 현재까지 구한 퀸까지들 중에서
    for(int i = 0; i < col; i++)
        // 1. 동일한 행에 있는 경우
        // 2. 대각선에 있는 경우 (좌상단~우하단)
        // 3. 대각선에 있는 경우 (좌하단~우상단)
        if(chess[i] == chess[col])
            return false;
        else if(abs(chess[col] - chess[i]) == col - i)
            return false;
        else if(i + chess[i] == col + chess[col])
            return false;
    
    // 서로 공격하는 퀸이 없는 경우
    return true;
}

// 0열부터 재귀 시작
void dfs(int col)
{
    if(col == N)
    {
        sol++;
        return ;
    }
    
    for(int row = 0; row < N; row++)
    {
        // 일단 퀸을 놓고
        chess[col] = row;
        
        // 서로 공격하는 퀸이 있는 지 확인
        if(check(col))
            // 없다면 다음 열로 넘어감
            dfs(col + 1);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    dfs(0);
    
    cout << sol;
    
    return 0;
}

 

 

● [백준] - [알고리즘 중급 1/3] - [531 - 브루트 포스 - 재귀 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	6603	로또	https://pirateturtle.tistory.com/301
2	1182	부분수열의 합	https://pirateturtle.tistory.com/302
3	14225	부분수열의 합	https://pirateturtle.tistory.com/303
4	14888	연산자 끼워넣기	https://pirateturtle.tistory.com/304
5	15658	연산자 끼워넣기 (2)	https://pirateturtle.tistory.com/305
6	14500	테트로미노	https://pirateturtle.tistory.com/306
7	16197	두 동전	https://pirateturtle.tistory.com/307
8	16198	에너지 모으기	https://pirateturtle.tistory.com/308
9	9663	N-Queen	https://pirateturtle.tistory.com/309
10	2580	스도쿠	https://pirateturtle.tistory.com/310
11	4574	스도미노쿠	https://pirateturtle.tistory.com/311
12	1987	알파벳	https://pirateturtle.tistory.com/312