[백준 - Python] 9663. N-Queen (완전 탐색)

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

9663번: N-Queen

 

백트래킹 대표 문제라고 해서

풀어야지 생각만 하고 미루다가

이제야 풀고 공부했다 ...

 

이 개념에 대한 설명은 몇 십번은 읽은 거 같은데,

개념적으로는 이해하기 그렇게 어려운 개념은 아닌데,

막상 코드로 구현하려면, 코드 작성이 수월하게 안되는 개념이다 ㅠ ㅠ ㅠ

 

 

.

.

.

 

 

백트래킹이란,

최적의 해를 찾는 과정에서, 유망하지 않은 후보 해에 대해 빠르게 포기하고

이전 단계로 되돌아가 다른 후보 해를 찾는 알고리즘 기법이다.

 

백트래킹과 DFS를 비교하며 설명해보면,

DFS는 깊이를 우선으로 하여 모든 노드를 방문하면서 탐색을 진행하는 반면에

백트래킹은 불필요한 탐색은 하지 않기 위해, 유망하지 않은 경우에는 탐색을 하지 않도록 하여

탐색해야 하는 경우의 수를 줄인다.

 

여기서 불필요한 탐색 부분을 제거하는 방법을 가지 치기(Pruning)이라고 부른다.

 

 

.

.

.

 

 

개념을 코드로 옮겨내면서 문제를 풀기 위해서는

많은 시간을 할애해서 개념을 익히고 연습을 해야한다!

 

해당 개념을 이용해 응용을 할 수 있는 건덕지가 많지는 않기 때문에

예제들을 많이 풀어보면서 기본적인 코드의 형태를 익히는 공부가 필요할 것 같다.

 

 

.

.

.

 

 

아이디어

체스에서 퀸은 상하좌우와 네 방향 대각선 어느 방향으로든

원하는 만큼 이동할 수 있다.

 

문제에서 NxN 체스판에 N개의 퀸을 서로 공격할 수 없게 놓아야 한다고 하였으므로

각 행마다 퀸을 하나 놓는다고 생각하고

첫 번째 행부터 시작해서 차례대로 아래의 행으로 이동해가면서 퀸을 배치한다.

 

퀸을 어떤 행의 특정 열에 놓으면서 확인해야 하는 것은

1. 같은 열에 퀸이 있는가

2. 대각선에 퀸이 있는가

    아래 행으로 내려가면서 퀸을 놓고 있기 때문에, 현재 놓으려는 퀸의

    1) 왼쪽 대각선 위에 퀸이 있는가

    2) 오른쪽 대각선 위에 퀸이 있는가

    를 확인해야 한다.

 

 

.

.

.

 

 

코드

import sys
input = sys.stdin.readline

# i행에 배치할 퀸에 대해서, 문제 조건에 맞게 놓을 수 있는지 확인하는 함수
def promising(i):
    for k in range(i):
        # 놓으려는 열에 이미 퀸이 있거나 왼쪽 오른쪽 위 대각선에 퀸이 있는 경우
        if abs(row[i] - row[k]) == i - k:
            return False
    return True


def backtracking(i):
    global result
    if i == N:  # 모든 행에 퀸 배치한 경우
        result += 1
        return
    for j in range(N):
        if check[j]:
            continue
        row[i] = j
        if promising(i):
            check[j] = True
            backtracking(i+1)
            check[j] = False


N = int(input())
row = [0] * N  # 각 행의 무슨 열 번호에 퀸을 놓았는 지 저장하는 변수
check = [False] * N     # 이미 퀸이 놓인 열 정보 저장하는 변수
result = 0       # 가능한 경우의 수 저장하는 변수

backtracking(0)

print(result)

 

코드 설명

우선 체스판의 가로 세로 크기이자 놓아야 하는 퀸의 개수인

N을 입력 받는다.

 

i행 j열에 퀸을 놓는다면

row 변수에 row[i] = j와 같은 형태로 정보를 저장한다.

즉, row 변수는 각 행의 무슨 열 번호에 퀸을 놓았는지 저장하는 변수이다.

 

check 함수는 특정 열에 퀸이 있는 지 없는 지를 확인하는 변수이다.

backtracking 함수에서 i 번째 행에 퀸을 놓는 과정에서

 i번째 행의 모든 열을 j로 확인하면서 check[j]를 통해

이전에 놓인 퀸들 중 j 열에 퀸이 이미 놓였는지 확인한다.

 

result 변수는

N개의 퀸을 모두 놓아서 문제 조건에 만족하는 경우를 하나 구했을 때 

1을 증가시킨다.

 

backtracking 함수 내부의 반복문을 보면

현재 퀸을 놓으려는 행의 모든 열 인덱스(j)에 대해서

이미 열에 퀸이 놓여있으면 다음 열을 확인해보고

열에 퀸이 놓여있지 않다면 

해당 위치가 이전에 놓인 퀸들에 의해서 공격을 받는 위치인지를 확인한다.

 

이를 확인해주는 함수가 promising 함수이다.

공격을 받을 수 있는 방향은 행 방향, 열 방향, 대각선 방향이 있는데

열 방향에 대해서는 이미 열 하나에 퀸 하나를 놓으면서 공격 받지 않도록 하였고

행 방향에 대해서노 backtracking 함수에서 check 변수를 통해 공격을 받지 않을 경우에 확인을 하고 있기 때문에

대각선 방향에 대해서만 공격 여부 통해 유망한 해인지 아닌지를 판단하면 된다.

 

대각선 방향에서 공격이 올 수 있는 경우는 왼쪽 위와 오른쪽 위 대각선 방향이 있는데

이 두 방향 모두, 각 퀸의 행 위치 좌표와 열 위치 좌표의 차이가 같다면

공격을 받을 수 있는 위치가 된다는 뜻이므로

해당 조건을 통해 공격 여부를 판단하도록 하였다.

 

탐색을 진행하다보면 아래의 그림과 같이 퀸을 어떤 열에도 둘 수 없고

돌아가야 하는 경우가 있을 것이다.

 

 

그런 경우에는, 아래 그림과 같이

다시 가능한 경우로 되돌아가서 새로운 경우에 대한 탐색을 진행하면 된다.

 

 

N이 4인 경우에 대해 탐색을 모두 마친 경우,

최종적인 상태공간트리의 모습이다.

 

 

참고 자료

https://blog.encrypted.gg/945

https://seen-young.tistory.com/50#c2