[백준/Python] N-Queen

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

9663번: N-Queen

출처 - https://velog.io/@suzieep/Algorithm-%EB%B0%B1%EC%A4%80-BOJ-9663-N-Queen-%ED%8C%8C%EC%9D%B4%EC%8D%AC

이 문제는 백트래킹 문제로 DFS를 사용하여 해결할 수 있었다. 근데 시간초과 문제 때문에 어려웠던 문제였다.

시간 초과를 해결하기 위해서는

1. 퀸을 배치할 수 있는지 확인할 때 break 를 사용하여 시간이 덜 걸리게 한다

2. pypy3 를 사용한다 (python3는 시간초과가 난다)

 

def queen(n, N) :
    global result
	
    if n == N: # 더 이상 탐색할 수 없는 경우 재귀함수를 빠져나감
        result += 1
        return
    else:
        for i in range(N): # 모든 열에 퀸을 놓을 수 있는지 확인
            row[n] = i
            for j in range(n):
                if row[n] == row[j] or abs(row[n] - row[j]) == n - j: # 퀸을 놓을 수 없다면 break
                    break
            else: # 퀸을 놓을 수 있다면 재귀함수 호출
                queen(n+1, N)
					
N = int(input()) # 퀸의 개수
result = 0 # 경우의 수
row = [0] * N # 각 행에서 퀸의 위치
queen(0, N)

print(result)

1. 필요한 정보를 입력 받고 각 행에서의 퀸의 위치를 알 수 알 수 있는 row 리스트를 만든다. N개의 퀸을 배치하기 위해서는 무조건 모든 행에 퀸을 배치해야 한다.

2. DFS를 수행한다.

    2-1. 각 행의 모든 열에 퀸을 놓을 수 있는지 확인한다.

    2-2. 퀸을 놓을 수 없다면 break 하여 for 문을 빠져나온다.

    2-3. 퀸을 놓을 수 있다면 재귀함수를 호출한다.

3. result를 출력한다.