[백준]9663 N-Queen(Python)

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

9663번: N-Queen

 

문제 접근 

 

모르겠어서 써치

잘 이해되지 않는 해설이 있기에 논의 필요(참고(1) 링크 첨부)

 

코드

import sys
input = sys.stdin.readline
n = int(input())

answer = 0
row = [0] * n

def is_possible(x):
    for i in range(x):
        if row[x] == row[i] or abs(row[x] - row[i]) == abs(x-i):    # 같은 열에 다른 퀸이 있는 경우 or 왼,오 대각선에 다른 퀸이 있는 경우
            return False

    return True

def n_queens(x):
    global answer
    if x == n:  # 모든 퀸을 놓았다는 의미
        answer += 1
        return

    else:
        for i in range(n):
            row[x] = i  # (x,i)에 퀸을 위치, x는 행 i는 열
            if is_possible(x):  # 해당 행에 위치할 수 있다면 타고 들어감
                n_queens(x+1)

n_queens(0)
print(answer)

 

 

회고

 

이해 안 가면 우선 외우고 시작..

행과 열이 있음에도 일차원으로 풀 수 있다는게 신기했다.

row[i] = j 라면 i는 행, j는 열

 

 

참고(1) 확인

https://chanhuiseok.github.io/posts/baek-1/

[백준] 9663번 - N-Queen

https://seongonion.tistory.com/103

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