[BOJ] 9663. N-Queen

백준 문제 주소 :

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

9663번: N-Queen

 

백준알고리즘을 시작한지 이제 한달이 되어가네요.

기본적인 문제들을 풀면서 이제 실력이 좀 늘은 것 같아요 ㅎㅎ

그래서 괜찮았던 문제 하나씩 블로그에 올려보려 합니다!

이번 문제는 Gold-5 문제인 N-Queen 문제인데요!

 

 

N*N 체스판에 N개의 퀸을 넣고 퀸이 서로 공격을 못 하게 해야합니다.

역시 처음에는 2차원 배열로 해결해야죠!!

True와 False를 사용하여 2차원 배열을 써본결과!!!

시 간 초 과...

 

하!! 그래서 찾아보다가 발견한 것!!

밑의 사이트에서 도움을 받았습니당 ㅎㅎ

https://savilla.tistory.com/2

[백준][9663번][DPS] N-Queen

 

열은 인덱스와 같으니까 1차원 배열로 안에 행의 값을 입력하자!

그래도 시간초과가 나서 계속 찾아본 결과, 제 코드는 pypy3로는 통과가 된다고 하더라구요?

바로 언어를 바꿔서 pypy3로 도전~~!!

 

그렇게 성공을 하였습니다 ㅎㅎㅎㅎㅎㅎ

성공한 코드는 재귀와 DFS를 썼습니다.

DFS는 밑의 사진을 보면 아는데요.

 

 

깊이 우선 탐색으로써 12 -> 7 -> 2 -> 6 -> 11 -> 6 -> 10 형식으로 찾습니다.

트리의 왼쪽 밑의 노드부터 찾는 거죠!

그래서 끝까지 내려 갈 수 있습니다.

다만, 이 코드에서는 밑까지 내려가긴 하지만 이 중 되는 것과 안되는 것을

중간중간 노드에서 break로 짜르기 때문에 시간이 좀 더 작게 걸립니다.

최악의 수로 15*15라면 원래 15!가 걸려야하지만 break문으로 인해 15!보다는 더 적게 걸리는 거죠.

그렇게 짠 코드는 아래와 같습니다.

 

# 퀸 놓아보기 함수
def build_queen(n, N) :
    global result           # 글로벌로 생성
    # 재귀 빠져나가기
    if n == N :
        result += 1
        return
    # 재귀 빠져나갈 수 없을 때 퀸을 놓아보고 이전 퀸들과 비교.
    else :
        for i in range(N) :
            row[n] = i
            # for문이 break 걸리지 않고 다 돌면 else(재귀) 실행
            for j in range(n):
                # 한 열에 하나씩 들어가므로 열 바교는 필요없다. 또한 대각선은 수학식을 생각해보면 쉽게 구할 수 있다.
                if row[j] == row[n] or (row[n] - n) == (row[j] - j) or (row[n] + n) == (row[j] + j):
                    break
            else : build_queen(n+1, N)

# 입력
s = int(input())

# 초기값 설정
result = 0
row = [300] * s

# 퀸 놓아보기 함수
build_queen(0, s)

# 출력
print(result)