n-queen 구현

n-queen 구현

 

백트레킹으로 누구나 한번쯤 들어봤을 문제.

간단하게 풀릴 것이라 예상하고 구현해봤는데 생각대로 잘 안된다.

 

첫 구현.

def way_on_queen(i, j, q):
    visited(i, j, q)

    dx = 1
    while i + dx < N:
        ni = i+dx
        visited(ni, j+dx, q)
        visited(ni, j-dx, q)
        visited(ni, j, q)
        dx += 1


def visited(i, j, q):
    if 0 <= j < N and grid[i][j]:
        grid[i][j] = False
        q.append((i, j))


def bt(i, cnt):
    global result
    if cnt == N:
        result += 1
        return

    for j in range(N):
        if grid[i][j]:
            q = []
            way_on_queen(i, j, q)
            bt(i+1, cnt+1)
            for r, c in q:
                grid[r][c] = True


N = int(input())

result = 0
grid = [[True] * N for _ in range(N)]
bt(0, 0)
print(result)

더 이상 개선할 부분이 없다고 생각했다.

queen을 놓으면 2차원 배열에 현재 행부터 끝까지 대각선, 열을 방문처리하는 것과

방문처리를 하면 백트래킹을 위해 q에 방문한 위치를 기억하도록 구현했다.

 

하지만 끝까지 시간초과에서 벗어날 수 없었다.

 

n = int(input())
check_row = [0 for i in range(n)]
check_leftcross = [0 for i in range(n*2)]
check_rightcross = [0 for i in range(n*2)]
ret = 0

def backtracking(cur):
    if cur==n:
        global ret
        ret += 1
        return 0
    for i in range(n):
        if check_row[i] or check_leftcross[n+cur-i] or check_rightcross[cur+i]:
            continue
        else:
            check_row[i] = 1
            check_leftcross[n+cur-i] = 1
            check_rightcross[cur+i] = 1
            backtracking(cur+1)
            check_row[i] = 0
            check_leftcross[n+cur-i] = 0
            check_rightcross[cur+i] = 0


for i in range(n//2):
    check_row[i] = 1
    check_leftcross[n-i] = 1
    check_rightcross[i] = 1
    backtracking(1)
    check_row[i] = 0
    check_leftcross[n-i] = 0
    check_rightcross[i] = 0
ret = ret*2

if n%2: #홀수일경우
    i=n//2
    check_row[i] = 1
    check_leftcross[n-i] = 1
    check_rightcross[i] = 1
    backtracking(1)
    check_row[i] = 0
    check_leftcross[n-i] = 0
    check_rightcross[i] = 0

print(ret)

우수한 코드를 풀이하면

check_leftcross의 2n개로 선언함으로써 대각선도 행과 열처럼 하나의 숫자로 표현할 수 있다는 성질을 이용한 것이다.

예를 들어 행이 4줄인 정사각형 모양이라면 총 7줄로 표현할 수 있다.

 

결과적으로 모든 행과 열, 대각선을 하나의 숫자로 표현할 수 있어서

2차원 배열이 아닌 1차원 배열로 표현하고 순회하지 않도록 구현할 수 있다.

 

참고

<built-in method builtins.input>

프로파일링 하다가 "input이 이렇게 오래걸린다고?" 하면서

나처럼 버그성 로그라고 생각한 사람이 있을까봐 적는다.

해당 함수의 시간은 입력을 받으려고 대기하는 순간부터의 시간을 의미한다.