2806. N-Queen

qjatjs123123·2023년 5월 11일
0

SW Expert Academy

목록 보기
18/18
post-thumbnail

2806. N-Queen

문제요약

NxN보드가 주어졌을 때 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 경우의 수는 몇 가지가 있을까?
퀸은 상하좌우,대각선 위에 있는 말을 공격할 수 있다.

문제풀이(처음 풀었던 답)

  1. 퀸이 처음 갈 수 있는 경로 16개중 처음 경로 (0,0)일 때를 생각해보자

    즉 색칠된 부분은 퀸이 놓을 수 없는 자리이다. 색칠되지 않는 부분만이 퀸이 놓을 수 있는 자리이다.

  2. 두 번째 깊이에서 퀸이 놓을 수 있는 경로 6개중 처음 경로 (1, 2)일 때를 생각해보자

    퀸이 갈 수 있는 경로를 색칠해주고 다음 DFS에서 색칠된 보드를 입력값으로 받는다.

  3. 세 번째 깊이에서 퀸이 놓을 수 있는 경로 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에 저장하고 오름차순 정렬을 한다. 그래서 그 결과가 중복된 것이 있으면 넘어가고 그렇지 않으면 계산해주는 것이다.

문제점 (TLE)

정확성에서는 맞지만 효율성 측면에서는 오류가 생겼다. 즉 제한시간 초과가 발생하였다. 왜냐하면 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))

이렇게 할 수 있는 이유는 한줄에 무조건 하나만 올 수 있다는 것이다.

이렇게하니 통과하였다.

profile
날마다 성장하는 개발자

0개의 댓글