NxN보드가 주어졌을 때 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 경우의 수는 몇 가지가 있을까?
퀸은 상하좌우,대각선 위에 있는 말을 공격할 수 있다.
퀸이 처음 갈 수 있는 경로 16개중 처음 경로 (0,0)일 때를 생각해보자
즉 색칠된 부분은 퀸이 놓을 수 없는 자리이다. 색칠되지 않는 부분만이 퀸이 놓을 수 있는 자리이다.
두 번째 깊이에서 퀸이 놓을 수 있는 경로 6개중 처음 경로 (1, 2)일 때를 생각해보자
퀸이 갈 수 있는 경로를 색칠해주고 다음 DFS에서 색칠된 보드를 입력값으로 받는다.
세 번째 깊이에서 퀸이 놓을 수 있는 경로 1개중 처음 경로(3, 1)일 때를 생각해보자
보면 N = 4이지만 퀸은 최대 3개밖에 놓을 수 없다. 이런식으로 하여 모든 경로에 따라 퀸이 4개 놓을 수 있는 개수를 계산한다.
def dfs(l, visited):
global ans
if l == n:
ans += 1
for row in range(n):
for col in range(n):
if visited[row][col]:
continue
tmp_visited = copy.deepcopy(visited)
direction = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1],[1, -1], [-1, -1], [-1, 1]]
tmp_visited[row][col] = True
for direct in direction:
new_row, new_col = row, col
while True:
new_row += direct[0]
new_col += direct[1]
if new_row < 0 or new_row == n or new_col < 0 or new_col == n:
break
tmp_visited[new_row][new_col] = True
dfs(l+1, tmp_visited)
해당 코드는 dfs함수이다. 5,6 번째 줄에서 nxn만큼 이중 포문이 도는 것을 볼 수 있을 것이다.
그리고 보드에 색칠되어 있다면(공격 가능하다면) 넘어가고 그렇지 않다면 상하좌우, 대각선을 보드에 색칠하는 것이다. 그것은 다음 깊이 DFS에서 색칠된 보드를 가지고 탐색한다.
첫 문제는 copy.deepcopy이다. 처음 얕은 복사를 사용하였더니 for문을 돌면서 copy의 본체 visited도 같이 변경되는 것이다. 그래서 깊은 복사를 사용하였다.
두번째 문제는 중복되는 것이다.
위 그림은 가능한 케이스 중 하나이다.
하지만 위에 중첩포문을 사용하게 될 경우 4x3x2x1 = 24가 된다. 왜냐하면 깊이가 1일 때 가능한 경우는 4개, 깊이가 2일 때 가능한 경우 3개, 깊이가 3일 때 가능한 경우 2, 깊이가 4일 때 가능한 경우 1이기 때문이다.
그래서 중첩을 해결해야 한다.
import copy
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
n = int(input())
ans = 0
dp = {}
def dfs(l, visited, stack):
global ans
if l == n:
if tuple(stack) not in dp:
ans += 1
dp[(tuple(stack))] = 1
return
for row in range(n):
for col in range(n):
if visited[row][col] or (row, col) in stack:
continue
tmp_stack = copy.deepcopy(stack)
tmp_stack.append((row, col))
tmp_stack.sort()
tmp_visited = copy.deepcopy(visited)
direction = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1],[1, -1], [-1, -1], [-1, 1]]
tmp_visited[row][col] = True
for direct in direction:
new_row, new_col = row, col
while True:
new_row += direct[0]
new_col += direct[1]
if new_row < 0 or new_row == n or new_col < 0 or new_col == n:
break
tmp_visited[new_row][new_col] = True
dfs(l+1, tmp_visited, tmp_stack)
arr = [[False for i in range(n)] for j in range(n)]
dfs(0, arr, [])
print("#" + str(test_case) + " " + str(ans))
stack과 딕셔너리가 사용된 것을 볼 수 있다. 즉 모든 위치를 stack에 저장하고 오름차순 정렬을 한다. 그래서 그 결과가 중복된 것이 있으면 넘어가고 그렇지 않으면 계산해주는 것이다.
정확성에서는 맞지만 효율성 측면에서는 오류가 생겼다. 즉 제한시간 초과가 발생하였다. 왜냐하면 1 깊이에서 모든 경우의 수를 생각했기 때문이다.
다르게 생각해서 보드는 NxN이고 퀸의 개수는 N이다. 즉 무조건 한 줄에 퀸 하나만 와야 한다.
그래서 이중포문이 아닌 포문(한줄)로 바꾸었다.
import copy
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
n = int(input())
ans = 0
dp = {}
def dfs(l, visited, stack):
global ans
if l == n:
ans += 1
return
for col in range(n):
if visited[l][col]:
continue
tmp_stack = copy.deepcopy(stack)
tmp_stack.append((l, col))
tmp_stack.sort()
tmp_visited = copy.deepcopy(visited)
direction = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1],[1, -1], [-1, -1], [-1, 1]]
tmp_visited[l][col] = True
for direct in direction:
new_row, new_col = l, col
while True:
new_row += direct[0]
new_col += direct[1]
if new_row < 0 or new_row == n or new_col < 0 or new_col == n:
break
tmp_visited[new_row][new_col] = True
dfs(l+1, tmp_visited, tmp_stack)
arr = [[False for i in range(n)] for j in range(n)]
dfs(0, arr, [])
print("#" + str(test_case) + " " + str(ans))
이렇게 할 수 있는 이유는 한줄에 무조건 하나만 올 수 있다는 것이다.
이렇게하니 통과하였다.