백준 9663번 N-Queen

해당 문제는 파이썬으로 제출할 경우 시간 초과가 발생하기 때문에 pypy3로 제출하였다.

---

문제 설명

 

isused는 퀸이 있는 위치, num은 체스판의 길이, count는 퀸을 놓는 방법의 수를 나타낸다. func의 인자로는 해당 위치의 행을 넣고 그 값이 체스판의 길이와 같아졌을 때 count를 1 증가시킨 후 함수를 종료한다.

 

 

b는 열을 의미하고 for문을 사용하여 모든 열을 검사한다. isused에 값이 있다는 것은 첫째줄이 아니라는 뜻이므로 queen을 놓을 수 있는지 검사한다.

isOk는 해당 위치인 (a,b)에 퀸을 놓을 수 있는지 판별하는 bool 값이다. 퀸을 놓을 수 있는지 판별하기 위해 검사해야할 것은 총 세 개다.

1) 같은 열에 있는가

2) 같은 대각선에 있는가

2-1) 왼쪽에서 오른쪽을 향하는 대각선인가

2-2) 오른쪽에서 왼쪽을 향하는 대각선인가

b == queen[1]이 1번을 뜻하고 a+b == queen[0]+queen[1]이 2-1번을 뜻하고 a-b == queen[0]-queen[1]이 2-2번을 뜻한다.  만약 3가지 경우 중 하나라도 해당하면 isOk값을 False로 바꾼다. isOk값이 True일 경우 해당 위치에 퀸을 놓을 수 있으므로 isused에 [a,b]를 append한 후 func함수에 다음 행을 인자로 넣어 호출한다.

 

 

isused에 값이 없으면 첫째줄이므로 isused에 해당 위치 [a,b]를 append한 후 다음 행을 인자로 넣어 함수를 호출한다.

 

전체 코드

isused = []
num = 0
count = 0


def func(a):
    global count
    if a == num:
        count += 1
        return

    for b in range(num):
        isOk = True
        if isused:
            for queen in isused:
                if b == queen[1] or a-b == queen[0]-queen[1] or a+b == queen[0]+queen[1]:
                    isOk = False
                    break
            if isOk:
                isused.append([a, b])
                func(a + 1)
                isused.pop()
        else:
            isused.append([a,b])
            func(a+1)
            isused.pop()
    return

def main():
    global num
    num = int(input())

    func(0)
    print(count)


if __name__ == "__main__":
    main()