[백준 9663번] N-Queen

문제 링크: 9663번 N-Queen

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

 

방법에 대한 고민을 3일, 시간 초과에 대한 고민을 2일 동안 했다. 결국 주변 사람들에게 도움을 구했지만...

 

가장 처음으로 생각해야 할 것은, 2차원 배열 board를 선언할 필요는 없다는 것이다. 어차피 한 행에 퀸은 하나밖에 들어가지 못하니까, 1차원 배열에서 row를 인덱스로 하여 col을 저장하면 된다.

 

그 다음으로는, check()에 대한 고민부터 할 수 있다.

check()는 (row, col)에 퀸을 놓고자 할 때, 해당 칸이 퀸을 놓을 수 있는 칸인지를 return하는 함수이다. 여기서 두 가지 사항에 대해 확인해야 한다.

 

1. 같은 열(col)에 퀸이 있는지를 확인해야 한다.

이를 위해서 bool[] queenCol을 선언하고, 어떤 행이든 퀸을 놓을 때마다 해당 열에 해당하는 값을 True로 바꾸어준다. 즉 (row, col)에 퀸을 놓고자 할 때, queenCol[col] = True를 실행한다.

 

2. 대각선(row+k, col+k)에 퀸이 있는지를 확인해야 한다.

0,0	0,1	0,2		0, n-1
1,0	1,1	1,2		1, n-1
2,0	2,1	2,2		2, n-1
			...	n-2, n-1
n-1, 0	n-1, 1	n-2, 2	n-1, n-2	n-1, n-1

bool queenRu[i]는 우상향 대각선들에 대해서 퀸이 있는지의 여부를 저장하는 배열로서, 좌측 상단부터 인덱스를 매기면, queenRu[i]에 해당하는 (row, col)들은 모두 row+col=i라는 조건을 만족한다.

bool queenRd[i]는 우하향 대각선들에 대해서 퀸이 있는지의 여부를 저장하는 배열로서, 좌측 하단부터 인덱스를 매기면, queenRu[i]에 해당하는 (row, col)들은 모두 col-row+n-1=i라는 조건을 만족한다.

 

이건 직접 하나 정도 체스판을 그린 후 생각해보면 좋다. 기본적인 아이디어는, '각 대각선에 번호를 매기고 해당 대각선이 갖는 row, col의 규칙을 찾아 그것을 인덱스로 변환하겠다'라는 생각이다.

 

어찌되었든, 아래 코드에서는 위 두 과정을 거친 후 모두 통과하면 check()가 True를 return한다.

 

nqueen()에서는 각 열에 대해서 퀸을 놓을 수 있는 자리인지 check()를 통해서 확인하고, 그것이 가능하다면 퀸을 놓으면서 queenCol[], queenRd[], queenRu[]의 값을 변경해준다. 그리고 그 다음 행에 퀸을 놓기 위해서 nqueen(n, row+1)을 호출한다. 단 여기서 배열은 전역변수로서 사용되고 있기에 복사되지 않으므로, 이전 값으로 바꾸어주는 과정이 필요하다. if check()를 통과했기에 이미 queenCol[col], queenRd[row+col], queenRu[col-row+n-1]은 False였을 것이기에 False로 바꾸어주면 된다.

 

n = int(input())
cnt = 0
queenCol = [False] * n # 해당 열에 퀸이 있는지의 여부
queenRd = [False] * (n*2-1) # 우하향 대각선에 퀸이 있는지의 여부
queenRu = [False] * (n*2-1) # 우상향 대각선에 퀸이 있는지의 여부

def check(n, row, col):
    global queenCol
    global queenRd
    global queenRu

    # 같은 열 체크
    if queenCol[col]: return False
    if queenRd[row+col] or queenRu[col-row+n-1]: return False
    return True

def nqueen(n, row): # row행에 퀸 놓기
    global queenCol
    global queenRd
    global queenRu
    global cnt

    for col in range(n):
        if check(n, row, col): # (row, col)이 퀸을 놓을 수 있는 자리라면
            if row == n-1:
                cnt += 1
                continue

            # 원래 값 저장
            # check를 통과한 순간 False인 것이 보장되므로 원래 값을 저장할 필요가 없다.
            # o1, o2, o3 = queenCol[col], queenRd[row+col], queenRu[col-row+n-1]

            # 다음 행에 퀸 놓기
            queenCol[col] = True
            queenRd[row+col] = True
            queenRu[col-row+n-1] = True

            nqueen(n, row+1)

            # 원래 값으로 되돌리기
            queenCol[col], queenRd[row+col], queenRu[col-row+n-1] = False, False, False

nqueen(n, 0)
print(cnt)