난이도

Gold 4

풀이 참고 유무

o

막힌 부분

퀸의 공격루트를 매번 조건으로 방문불가 처리를 하는 감을 못잡음
퀸의 공격루트를 매 반복때마다 방문처리를 하면 무조건 시간초과가 날 것 같아서 감을 잡지 못함

문제

문제 바로가기

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

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

입력

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

출력

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

예제 입력

8

예제 출력

92

문제 검토

고민하는 것에 시간을 너무 허비하고 싶지 않아서 30분 정도 고민하다가 풀이와 힌트를 보고 이해하고 다시 전략을 세운 뒤 풀어보았다.

풀이(python)

Python

from sys import stdin
input=stdin.readline                
n=int(input())
answer=0
row=[0] * n
def queen_check(r):
    for x in range(r):
        #열이 같은지,행이 같은지, 대각선인지
        if row[r]==row[x] or abs(row[r]-row[x])==abs(r-x):
            #해당된다면 그곳에 놓을 수 없다.
            return False
    return True

def dfs(r):
    global answer,n
    #다 도달한 것임으로 이제 그만
    if r==n:
        answer+=1
        return
    else:
        #n열까지 탐색
        for x in range(n):
            #r번째 row의 x열에 퀸을 놓을 수 있는지 탐색하겠다.
            row[r]=x
            if queen_check(r):
                dfs(r+1)
dfs(0)
print(answer)  

아이디어

#일단 해당 행의 0~n-1의 열로 반복문을 돌릴 것이다.
#1. 먼저 0행에 0열에 퀸을 놓을 수 있는지 확인 넣을 수 있다면
#2. 1행으로 재귀해 0열확인 안되니까 1열도확인 하면서 된다면 또 2행으로 재귀
#3. 이렇게 하여 n행까지 도달하게 되면 answer+1
#4. 그 다음 이제 0행의 1열에 퀸을 놓을 수 있는지 확인 이후 1행의 0열부터 다시 가능한지 확인한다.
#5. 이 과정을 반복 결국 가장 큰 반복은 0행의 0열부터 n-1열까지이고 그 밑 행은 0행의 열이 정해진 뒤로 또 차례로 정해진다.abs
#6. 이 문제에서는 in으로 탐색하는 것이 아니고 1차원 배열을 초기화하며 확인하는 것이기 때문에 pop이나 remove가 필요없는 백트랙킹이다.

시간 복잡도

#1 0행부터 n행까지 반복하면서 일단 n
#2 확인하는 과정에서 n에 가까이 소요됨 n^2
#3 가능한 열을 찾는 과정에서 또 n정도 소요됨 n^3
#4 한번 수행하는데는 약 3,375번에 연산을 수행하지만 이 과정을 무수히 수행하기에 시간이 많이 소요될 것이다.
#5 보통 중복이 없는 백트랙킹은 O(n!) 정도로 보는데 15!은 대충 1천억 정도 된다.
#6 이 문제에서 주어진 시간은 10초지만 파이썬 한정으로 더 많이 줄 것이다.abs
#7 파이썬으로는 풀 수 없을 것 같고 pypy로 간당간당하게 합격할 수도 있을 것 같다.

자료구조

#1차원 리스트:row

퀸은 열과 행이 같지 않고 x와 nx y와 ny의 좌표를 각각 뺀 결과의 절대값이 같다면 대각선이기 때문에 이 조건에 해당되면 False이다.

걸린 시간

1:02:55 (30분 때 풀이와 힌트를 봄)

총평

이 문제에서의 중요한 것은 퀸이 매 반복때마다 추가되기 때문에 조건이 추가된다는 것이다.
한정된 조건 속에서 퀸을 놓을 수 있는 노드를 찾아야 한다.

당연히 처음에는 2차원배열을 생각하고 체킹하면서 풀려고 했으나 시간 초과가 날 것이 분명했다.

row[]의 값을 col로 하여 row와 col을 정하는 것이 획기적인 방법이었다.
row[0]=col 부터 col을 0부터 n까지 반복하며 퀸을 놓을 수 있는 위치인지 확인하고 col을 고정한 다음 row[1]의 col을 0부터 n까지 찾고 자리를 정하고 하는 반복을 하며 문제를 구하는 방식이다.

백트랙킹을 할 때 최적화가 가장 중요하다고 생각한다.
이런식으로 약간 깊게 조건을 정하고 픽스해가며 2차원 배열의 문제를 푸는 방식도 잘 생각해 보아야한다.