파게로그
[백준 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)
'콤퓨타 왕왕기초 > PS' 카테고리의 다른 글
[백준 2800번] 괄호 제거 (0) | 2020.11.24 |
---|---|
[백준 1662번] 압축 (0) | 2020.11.24 |
[백준 1003번] 피보나치 함수 (0) | 2020.11.22 |
[백준 9996번] 한국이 그리울 땐 서버에 접속하지 (0) | 2020.11.21 |
[백준 2748번] 피보나치 수 2 (0) | 2020.11.20 |