9663. N-Queen (Python)

9663번: N-Queen

 

풀이

 백트래킹을 사용하는 대표적인 문제다. 각 행이나 열마다 퀸은 하나씩만 존재할 수 있고 대각선에 퀸이 있는지를 체크해야한다. 처음에는 함수에 열의 정보는 리스트를 활용해서 전달하고 대각선은 왼쪽 위와 오른쪽 위를 하나씩 체크하도록 for문을 사용하였다. 그렇게 했을 때 아래와 같이 시간이 많이 걸려 다른 방식을 찾아보았다.

 

 먼저 보드에 퀸이 놓여져 있는 위치는 1차원 리스트를 통해서 표현할 수 있다.

 위의 그림과 같이 board[n] = m 은 n행 m열에 퀸이 놓여져 있음을 의미한다. 이를 사용하여 같은 열에 퀸을 놓는지를 체크할 수 있다. 대각선에 퀸이 놓여져 있는지를 확인하는 법은 다음과 같은 식을 이용하면 된다.

행의 차이 = 열의 차이의 절댓값

 즉, 코드로 아래와 같이 작성하여 한 번의 for문으로 같은 열인지, 대각선 상에 있는지를 체크할 수 있다.

for j in range(row):
	if board[row] == board[j] or (row - j == abs(board[row] - board[j])):
		possible = False 
		break

위의 방식을 사용했을 때 시간이 줄어들었음을 볼 수 있다.

 

 

코드

[개선된 코드]

def queen(row):
    if row == N: # 모든 행에 퀸을 놓았으므로 res 1 증가시키고 종료 
        global res
        res += 1
        return

    for i in range(N): # 0열 ~ N-1열 까지
        if check[i]: # 이미 사용된 열이면 continue 
            continue 

        board[row] = i # row행 i열에 퀸을 놓는다 

        possible = True 
        for j in range(row): # 0행 부터 row-1행 까지 돌면서
            # 같은 열에 놓았는지, 같은 대각선 상에 놓았는지를 체크 
            if board[row] == board[j] or (row - j == abs(board[row] - board[j])):
                possible = False # 공격할 수 있는 위치면 놓을 수 없음을 체크하고 break
                break 
        
        if possible: # 가능한 위치에 놓였을 경우 
            check[i] = True 
            queen(row+1) # 다음 행에 대하여 반복 수행 
            check[i] = False 


if __name__ == '__main__':
    N = int(input())
    check = [False for _ in range(N)] # 해당 열이 사용되었는지를 체크하기 위한 리스트
    board = [0 for _ in range(N)] # board[n] = m은 n행 m열에 퀸을 놓았음을 의미한다 
    res = 0

    queen(0)

    print(res)

 

[개선전 코드]

def queen(row, columns):
    if row == N:
        global res
        res += 1
        return

    for i in range(N):
        if i in columns:
            continue

        possible = True
        # 왼쪽 위 대각선 체크
        for j in range(N):
            nx, ny = row - j, i - j

            if nx < 0 or ny < 0:
                break

            if check[nx][ny]:
                possible = False
                break

        # 오른쪽 위 대각선 체크
        for j in range(N):
            if not possible:
                break
            nx, ny = row - j, i + j

            if nx < 0 or ny >= N:
                break

            if check[nx][ny]:
                possible = False
                break

        if possible:
            check[row][i] = True
            queen(row+1, columns + [i])
            check[row][i] = False 


if __name__ == '__main__':
    N = int(input())
    check = [[False for _ in range(N)] for _ in range(N)]
    res = 0

    queen(0, [])

    print(res)