121. 9663(N-Queen)

※ 본 코드는 pypy3으로 제출해야 합니다.

N = int(input())
visited = [False] * N
QueenNum = [0] * N
cnt = 0


def DFS(depth):
    global cnt
    if depth == N:
        cnt += 1
        return

    for i in range(N):
        if not visited[i]:  
            QueenNum[depth] = i  

            isQLocated = False
            for j in range(depth):
                if abs(QueenNum[depth] - QueenNum[j]) == abs(depth-j):                   
                    isQLocated = True
                    break

            if not isQLocated:
                print(">>",i,depth,QueenNum[depth])
                visited[i] = True
                DFS(depth+1)
                visited[i] = False


DFS(0)
print(cnt)

문제요약

Queen이 N개 있는데 N*N 체스판에서 Queen이 서로 공격하지 못하게 위치 경우의 수를 구하시오.

설명

N이 4일때를 예를 들어보자.(4*4에서는 2가지가 존재한다.)

다음과 같은 경우에 Queen이 서로 공격할 수 없으므로 문제에 조건이 맞는다.

참고로 (2, 0) 은 (QueenLocation, depth) 혹은 (i, depth) 이다.

 

QueenLocation = [0] * N

먼저 Queen에 위치를 0으로 초기화 해준다.

 

깊이우선 탐색이므로,

if depth == N:
        cnt += 1
        return

끝 깊이까지 도달 했을 때 (n개의 퀸이 서로 공격하지 않는다면) 카운트를 증가시키고 return한다.

 

        if not visited[i]:  
            QueenNum[depth] = i

만약 탐색한 경우가 False라면 QueenNum을 부여한다. 

 

            isQLocated = False
            for j in range(depth):
                if abs(QueenNum[depth] - QueenNum[j]) == abs(depth-j):                   
                    isQLocated = True
                    break

퀸이 공격을 하는 위치인지 확인을 한다.

 

 

퀸이 공격을 하지 않는 경우는 다음과 같다.

abs(QueenNum[depth] - QueenNum[j]) == abs(depth-j)

 

대각선을 검토한다.

예를 들어 2,2에서 탐색한다고 하자.

행의 차, 열의 차가 (1,1) (1,3) (3,1) (3,3) 으로 나아간다면, 대각선을 컴토하는 것이다.

 

한번 확인을 해보자면 2-1 2-1 같으므로 대각선, 2-1 3-2 같으므로 대각선, 2-3 2-1 (절대값)같으므로 대각선, 2-3 2-3(절대값) 같으므로 대각선.

따라서 대각선으로 뻗어나가는 것을 알 수 있다.

 

	if not isQLocated:
                visited[i] = True
                DFS(depth+1)
                visited[i] = False

상하를 탐색했을 때 퀸이 없다면 DFS 재귀를 실행할 것이다.

DFS를 통해 대각선을 탐색하게 된다.

그 이유는 i는 x값으로 볼 수 있고 depth는 y값으로 볼 수 있다.

for문으로 인해 i가 증가할 수 있고, depth가 DFS(detph+1)을 통해 증가 할  수 있다. (공격하지 않는 조건 2번에 부합.)

상하좌우 에서 걸려 i만 증가할 수 있다. (공격하지 않는 조건 3번에 부합.)