[백준 / BOJ] 9663번 N-Queen (C++, Python)

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

9663번: N-Queen

---

문제

---

문제 풀이

유명한 백트래킹 문제다. 옛날에 알고리즘을 공부할 때 접해본 적이 있어 빨리 풀었지만, 아마 처음 접했다면 시간을 엄청 오래 썼을 것 같다.

 

우선 N-Queen 게임에 대한 이해가 필요하다.

1. 퀸의 특성상 체스판 한 행에 한 개의 퀸만 존재할 수 있다.
2. 서로 다른 퀸은 대각선상에 존재할 수 없다.

 

한 행씩 퀸을 배치하면서 총 배치 횟수가 N이 된다면 모두 배치를 성공했다는 뜻이므로 해당 변수를 1씩 증가시키는 방식으로 풀 수 있다. 그래서 자연스럽게 dfs의 매개변수로 몇번째 행인지를 넣어주어야 한다.

또한, 이 문제에서 굳이 visited로 2차원 배열을 사용할 필요가 없다. 어차피 1번째 열에 퀸을 넣어놓았으면 그 열에는 퀸이 들어갈 수 없으므로 1차원 배열을 사용해도 된다. 하지만 사실 내가 이 아이디어를 직관적으로 떠올릴 수 있었는지 물어본다면 잘 모르겠다. 2차원 배열로 풀어도 문제는 없다.

 

C++ 상세 풀이

N-Queen 게임의 조건을 if문으로 만드는 방법은 다음과 같다.

 

bool isPossible(std::vector<int> &v, int row) {
    for (int i = 0; i < row; ++i) {
        // 일차원 배열에서 같은 위치에 있으면 안됨, 대각선상에 있으면 안됨
        if (v[i] == v[row] || abs(v[i] - v[row]) == row - i) return false;
    }
    return true;
}

우선 v[i] == v[row]로 일차원 배열에서 같은 위치에 있다는 뜻은 같은 열에 위치한다는 뜻이므로 조건에 위배된다.
대각선 조건이 살짝 까다로운데, 우선 대각선에 존재한다면 x, y 좌표의 차가 같을 것이다. 여기서는 v[i]가 의미하는 것이 x좌표이고 i가 의미하는것이 y좌표이므로 위의 조건처럼 쓸 수 있을 것이다. row는 항상 i보다 크므로 절댓값을 신경쓰지 않아도 된다.

 

void dfs(std::vector<int> &v, int N, int row) {
    if (row == N)
        cnt++;
    else {
        for (int i = 0; i < N; ++i) {
            v[row] = i; // 현재 행 위치에 열 값을 할당한다.
            // 해당 행, 열에 존재할 수 있다면 다음 행을 검사한다.
            if (isPossible(v, row)) dfs(v, N, row + 1);
        }
    }
}

row == N일 시, 모든 행을 정상적으로 돌았을 경우이므로 퀸을 놓는 방법의 수인 cnt 변수를 하나 증가시켜준다.
이외에는 N만큼 for문을 돌아 행을 채워주는 코드를 작성해주면 된다.

 

Python 상세 풀이

N-Queen 게임의 조건을 if문으로 만드는 방법은 다음과 같다.

 

def isPossible(row):
    for i in range(row):
        # 일차원 배열에서 같은 위치에 있으면 안됨, 대각선상에 있으면 안됨
        if res[i] == res[row] or abs(res[i] - res[row]) == row - i:
            return False

    return True

우선 res[i] == res[row]로 일차원 배열에서 같은 위치에 있다는 뜻은 같은 열에 위치한다는 뜻이므로 조건에 위배된다.
대각선 조건이 살짝 까다로운데, 우선 대각선에 존재한다면 x, y 좌표의 차가 같을 것이다. 여기서는 res[i]가 의미하는 것이 x좌표이고 i가 의미하는것이 y좌표이므로 위의 조건처럼 쓸 수 있을 것이다. row는 항상 i보다 크므로 절댓값을 신경쓰지 않아도 된다.

 

def dfs(row):
    global cnt

    if row == N:
        cnt += 1
        return
    else:
        for i in range(N):
            res[row] = i # 현재 행 위치에 열 값을 할당한다.
            # 해당 행, 열에 존재할 수 있다면 다음 행을 검사한다.
            if isPossible(row):
                dfs(row + 1)

row == N일 시, 모든 행을 정상적으로 돌았을 경우이므로 퀸을 놓는 방법의 수인 cnt 변수를 하나 증가시켜준다.
이외에는 N만큼 for문을 돌아 행을 채워주는 코드를 작성해주면 된다.

 

코드 전문

C++

Python

 

소감

유명한 백트래킹 문제답게 어려운 문제다.