2806. N-Queen

본 글의 내용은 절대적으로 좋은 코드라는 보장이 없습니다. 글을 읽어보시다가 "이 사람은 이런 식으로 짰구나. 되게 허접하게 짰네?" 라는 생각이 드시면 댓글을 통해서 좋은 가르침과 의견을 주시면 감사합니다!!

---

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB&categoryId=AV7GKs06AU0DFAXB&categoryType=CODE

SW Expert Academy

이번 N-Queen 문제는 두 가지 풀이 방법이 있습니다.

1. N-Queen 문제를 처음 접하는 제가 직접 생각해낸 투박한 방법
2. 다른 사람이 푼 문제를 보고 영감받고 다시 푼 방법

차례대로 소개하겠습니다.

 

1. N-Queen 문제를 처음 접하는 제가 직접 생각해낸 투박한 방법

기본 아이디어

• 새로 퀸을 놓을 때마다 놓을 수 없는 자리를 업데이트하면서 재귀 함수를 활용해서 푼다.
• 재귀 깊이가 N과 동일해지면 count를 하나 늘려준다.

from copy import deepcopy

def checkVisit(x, y, _list):
    for d in range(8):
        new_x = x
        new_y = y
        while -1 < new_x < N and -1 < new_y < N:
            _list[new_y][new_x] = 1
            new_x += dx[d]
            new_y += dy[d]
    return _list

def dfs(y, cur_board):
    if y == N:
        global count
        count += 1
    else:
        for x in range(N):
            if cur_board[y][x] == 0:
                new_board = deepcopy(cur_board)
                checkVisit(x, y, new_board)
                dfs(y+1, new_board)

T = int(input())

dx = [0, 0, -1, 1, 1, 1, -1, -1]
dy = [-1, 1, 0, 0, 1, -1, 1, -1]

for tc in range(T):
    N = int(input())
    board = [[0 for _ in range(N)] for _ in range(N)]
    count = 0

    dfs(0, board)

    print('#{} {}'.format(tc+1, count))

문제점

• 체스 판을 순회하면서 반복 작업을 상당히 진행해야 한다.
• 체스 판의 정보를 넘겨줄 때 바꾼 정보를 재귀 작업을 마치고 돌아올 때 다시 되돌려줘야 하는데 바꾼 정보를 따로 저장해놨다가 되돌리는 작업이 귀찮아서 deepcopy로 아예 새로 리스트를 만들어서 넘겨줬는데 이 작업이 실행 시간을 오래 걸리게 만드는 것 같았다.

그래서 다른 N-Queen 풀이법들을 살펴보고 괜찮다고 생각한 방법을 사용해서 풀이한 방법입니다.

 

2. 다른 사람이 푼 문제를 보고 영감받고 다시 푼 방법

 

•  

제가 만듬

row는 말 그대로 행 정보이고 diag1은 우상에서 좌하로 그어지는 대각선 정보, diag2는 좌상에서 우하로 그어지는 대각선 정보이다. 해당 값이 같을 때 동일한 선에 속한 요소임을 알 수 있다.

위 방법을 사용하면 실제 이차원 리스트를 새로 만들어서 일일이 체스판을 순회하면서 방문 정보를 체크해줄 필요 없다.

 

def dfs(y):
    if y == N:
        global count
        count += 1
        return

    for x in range(N):
        if row[x] or diag1[x + y] or diag2[x - y]:
            continue

        row[x] = diag1[x + y] = diag2[x - y]= 1
        dfs(y+1)
        row[x] = diag1[x + y] = diag2[x - y]= 0


T = int(input())

for tc in range(T):
    N = int(input())
    count = 0
    row, diag1, diag2 = [0 for _ in range(N)], [0 for _ in range(2 * N - 1)], [0 for _ in range(2 * N - 1)]

    dfs(0)

    print('#{} {}'.format(tc+1, count))

 

 위 코드를 돌린 결과 엄청 빨라지고 코드도 엄청 짧아졌다. 선조들의 지혜가 소중함을 느낄 수 있었다.