[BOJ] 9663 N-Queen - Python

🤔 문제

---

9663번: N-Queen

 

😀 풀이

---

위 문제는 백트래킹으로 유명한 N-Queen 문제입니다.

 

처음에는 해당 문제를 2차원 배열을 사용하여 퀸들의 위치 정보를 담아 풀이를 하려했는데 구글링 도중 1차원 배열을 사용해 푸는 좋은 방법이 있어 해당 부분을 차용해보았습니다.

 

자세한 내용은 아래와 같습니다.

rows라는 1차원 배열을 가지고 퀸들의 정보를 담습니다.

만약 rows[i] = j 라는 값을 가진다면 이는 i 행의 j 열에 퀸이 놓여져있다라는 의미가 됩니다. 

 

또한 문제 풀이 과정에서 두 가지 함수를 만들어 사용했습니다.

 

 

1. put_queen : 특정 행에 퀸을 놓아보는 함수

# r행에 퀸을 놓아보기
def put_queen(r):
    global answer
    if r == n: # 퀸을 n행까지 조건에 맞게 다 채워 넣은 경우
        answer += 1
        return
    
    for i in range(n):
        rows[r] = i
        if is_valid(r):
            # 해당 자리에 놓을 수 있다면 다음행으로!
            put_queen(r + 1)

 

2. is_valid : 특정 자리에 퀸을 놓았을 때 해당 자리가 놓아도 되는 자리인지 체크하는 함수 

# 현재 놓은 퀸 자리가 유효한지 체크
def is_valid(r):
    for i in range(r):
        # 세로 체크
        if rows[i] == rows[r]:
            return False
        # 대각선 체크
        if abs(r - i) == abs(rows[r] - rows[i]):
            return False
    return True

is_valid에서 체크를 하는 과정을 보면 for문을 0 ~ r -1 까지만 돌리는 것을 확인할 수 있습니다. 이는 r행에 퀸을 놓았을 때 r행의 윗 부분만 확인해주면 되기 때문입니다. 아래 부분은 앞으로 놓을 예정이기 때문이죠!

 

또한 대각선 체크 역시 위 코드와 같은 방법을 사용하면 왼쪽 대각선과 오른쪽 대각선을 한꺼번에 확인해줄 수 있습니다.

 

 

 

---

💻 전체 풀이 코드는 아래와 같습니다.

n = int(input())
answer = 0
rows = [0] * n

# 현재 놓은 퀸 자리가 유효한지 체크
def is_valid(r):
    for i in range(r):
        # 세로 체크
        if rows[i] == rows[r]:
            return False
        # 대각선 체크
        if abs(r - i) == abs(rows[r] - rows[i]):
            return False
    return True

# r행에 퀸을 놓아보기
def put_queen(r):
    global answer
    if r == n:
        answer += 1
        return
    
    for i in range(n):
        rows[r] = i
        if is_valid(r):
            # 해당 자리에 놓을 수 있다면 다음행으로!
            put_queen(r + 1)
    
put_queen(0)
print(answer)