백준 9663 N-Queen - Python

출처 :

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

9663번: N-Queen

풀이:

n = int(input())

ans = 0
row = [0]* n

def right(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 queen(x):
    global ans  # 함수 안에서 ans 값이 변할 수 있도록 해줌
    if x == n:
        ans += 1
        
    else:
        for i in range(n):
            row[x] = i   #[x,i]에 퀸을 두겠다. 
            if right(x):
                queen(x+1)

queen(0)
print(ans)

전체코드는 위와 같고 하나하나 보려고 한다.

 

일단 설명하기전 백트래킹을 대할 때는 뒤에서 부터 생각하면서 접근해야한다는 점을 강조하고 싶다.

 

우선 하나하나 살펴보면 

ans : 성공한 경우의 수를 1씩 증가해가기위해 0으로 선언.

row : [0]을 원하는 판의 개수만큼 설정해준다. 그래서 우리가 자주 쓸 기술은 [3,4] 좌표를 row[3]=4 로 표현할 것이다.

 

1. checking system

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

x는 행의 위치이다. 퀸이 서로 안만나게 하는 방법은 1. 같은 열에 없을 때 2. 같은 행에 없을 때 3. 대각선으로 존재 하지 않을 때다.

1에 대해서는 다음과 같은 row[x] = row[i] 일 땔를 제거 해주면 된다. 예를 들어 row[1] = 2 (1,2) 이고 row[0] = 2 (0,2) 이면 False로 기록할 것이다.

2에 대해서는 우리는 뒤에서 살펴볼 코드에서 한 행에 한번만 입력하게 설정할 것이다. 그래서 자동으로 넘어가자

3에 대해서는 (4,5) 라고 하면 이것에 대각선은 (3,6),(2,7) // (3,4),(2,3) 으로 각 행과 열의 차이를 빼주면 값이 같아야한다.

-> row[x] - row[i]  == x - i 이걸 확인하면 될 것이다.

 

2. queen 두기

def queen(x):
    global ans  # 함수 안에서 ans 값이 변할 수 있도록 해줌
    if x == n:
        ans += 1
        
    else:
        for i in range(n):
            row[x] = i   #[x,i]에 퀸을 두겠다. 
            if right(x):
                queen(x+1)

queen(0)
print(ans)

 1. global 함수 - 저걸 씀으로서 함수 안에서 ans 값을 변경하고 저장해주는 역할을 해준다. 저걸 쓰지 않으면 ans = 0 으로 출력된다.

2. 행이 7까지 있는데 8까지 성공적으로 도달하면 ans 에 1을 더해준다.

3. 퀸을 어디에 둘 지를 정하는건데 x로 행의 위치를 잡았다면 다음 0~7 까지 열에 값을 넣어줘서 값을 넣은 다음 그 다음 행으로 넘어가서 다시 위치를 두면서 성공했는지 right 함수로 확인하며 진행한다.

 

아이패드 산김에 자랑 ㅋㅋ ㅎㅎㅎ 빨간색으로진행하고 끝나면 파랑색으로 다시 진행 되면서 ans 가 추가된다고 보면 편한다.