[백준 9663번-N-Queen]-파이썬

solved.ac 난이도 :  GOLD5

백준  9663번- 파이썬 풀이

 

<문제>

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

9663번: N-Queen

<풀이>-백트랙킹

이번 문제는 대표적인 백트랙킹 문제인 N-Queen이다. 필자는 처음 이문제를 풀때 2차원 배열을 이용해야하나 했지만 그렇게 하게되면 너무 복잡해진다. 그래서 일차원배열을 이용해 문제를 풀었다. 그 과정은 다음과 같다.

 

1)체스판에 체스 놓기

 

일차원 배열의 한 위치에 값을 rows[i] = a 와 같이 값을 저장시킨다. 이것은 체스판의 [i,a]에 체스를 둔다는 말과 같은 의미로 생각하면 이해하기 편하다. 이때 체스를 둘때 0행부터 n행까지 즉 위에서부터 아래로 순서대로 둔다고 가정하고 문제를 푼다.

 

2)다른 체스와 공격을 주고받을 수 있는지 없는 지 확인한다.

 

서로 공격을 주고받을수 있는지 없는지 확인하기 위해서 두개의 체스가 같은 열에 있는지, 혹은 대각선상에 있는지 확인하면 된다.

 

이때 같은 행에 있는지는 확인하지 않는 이유는 우리는 문제를 풀때 위에서 부터 아래로 한행에 하나의 체스만 둘거기 때문이다. 

 

그리고 대각선상에 있는지 확인하는것도 위에서부터 아래로 체스를 둔다고 생각하고 문제를 풀거기 때문에 위에 대각선만 확인해주면 된다.

이러한 과정을 코드로 옮기면 다음과 같다.

 

def check(x):
    for i in range(x):
        if row[x] == row[i] or abs(row[x]-row[i]) == abs(x-i):
            return False
    return True

3) 재귀적으로 함수 호출하기

 

한행에 체스를 두고 만약 그 위치가 다른 체스와 공격을 서로 주고받지 못하는 위치라면 다음 행에 체스를 두기 위해 재귀적으로 함수를 호출한다.

 

만약 문제의 조건을 만족하는 위치가 아니라면  현재 행에서 다른 위치에 체스를 둔다.

 

그리고 각 행마다 체스를 놓은 위치가 조건을 만족해 n번째 행까지 호출이 완료 됐다면 체스를 둘수 있는 방법의 갯수를 저장하는 ans변수에 1을 더해준다음 함수를 종료하고 (n-1)행에 다른 위치도 가능한지 살펴본다.

 

예를 들어 8*8체스판에 체스를 둘때 함수의 호출은 다음과 같이 이뤄진다.

 

1행->2행->3행->4행->5행->6행->7행->8행->7행->더이상 둘곳이 없다면->6행..................

 

def n_queens(x):
    global ans
    if x == n:
        ans+=1
        return
    else:
        for i in range(n):
            row[x] = i
            if check(x):
                n_queens(x+1)

 

 

<코드>-파이썬

 

n = int(input())

ans = 0

row = [0]*n

def check(x):
    for i in range(x):
        if row[x] == row[i] or abs(row[x]-row[i]) == abs(x-i):
            return False
    return True
def n_queens(x):
    global ans
    if x == n:
        ans+=1
        return
    else:
        for i in range(n):
            row[x] = i
            if check(x):
                n_queens(x+1)
n_queens(0)
print(ans)

-마치며-

백트랙킹 문제의 경우 삼성전자 sw역량테스트에 자주 나오는 유형의 문제이므로 꼭 중요하게 다뤄서 풀어야 한다. 먼저 기초적인 문제부터 풀어 어떻게 알고리즘이 작동하는지 파악한다음 응용문제들을 푸는것이 중요한거 같다. DFS문제를 푸는것이 백트랙킹 문제를 푸는데에 도움이 될거 같다.