9663번 N-Queen

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

#코드 출처: https://seongonion.tistory.com/103

n = int(input())

ans = 0
row = [0] * n

def is_promising(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
    else:
        for i in range(n):
            row[x]=i
            if is_promising(x):
                n_queens(x+1)
    
    
n_queens(0)
print(ans)

느낀 점:

내 힘으로는 풀지 못했다... 이해는 되었지만 직접 구현해보라고 하면 다시 헷갈릴 것 같다.

지금으로서는 백트래킹이 내 최대 약점인 것 같다.

내가 구현하려할때는 Naive하게 접근하다보니 코드가 길어졌는데, 위 코드는 Key Point를 잘 잡고 풀어서 코드가 깔끔하게 떨어진 것 같다.

2차 시도

#반복문을 통해서 모든 행에 하나씩 둘 때까지 한다 (모든 행인 이유는 똑같은 행에는 queen이 존재할 수 없기 때문)
#is promising: 만약에 직선으로 곂치거나, 대각선으로 곂치면 아예 재귀를 돌리지 않고 False를 return하고 다음 열을 탐색한다.
#곂치지 않는다면 계속해서 재귀적으로 찾아나간다. True라면 다음 행을 탐색한다. 
#위에서부터 말을 두고 있기 때문에, 이미 둔 위랑만 비교를 하면 된다.

N = int(input())
#index를 행, 값을 열로 갖는 배열
row = [0] * N 
cnt=0

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

    return True
        
def solution(x):#x는 행 값
    global cnt
    #행을 도는 반복문
    if x == N:
        cnt+=1
        return 
    #(x는 재귀할때마다 +1해서 들어가기 때문에) 열을 탐색
    for i in range(N):
        #이미 row[x]에 값을 넣었기 때문에 x를 is_promising에 넣어줌
        row[x] = i
        if is_promising(x) == True:
            solution(x+1)
            #return이 있으면 안됨. 여기서 True였어도 깊이 탐색하다가 False나면 다시 for문 돌아야 해서
    return #여기 return은 있어도 되고 없어도 됨

solution(0)
print(cnt)

이번에는 거의 다 틀은 잡았는데, 역시나 return을 써주면 안되는데 써준다던가, parameter를 잘못준다던가 하는 실수가 있었다.
선언한 변수와 함수에 대한 개념이 덜 잡혀있어서 그런 것 같다.

• 계속 시간초과나서 찾아봤더니 pypy3로는 된다.