[백준] [Python] N-Queen - 백트래킹 - [대표예제]

www.acmicpc.net/problem/9663

9663번: N-Queen

 

 

 

 

Python

n = int(input())

cnt = 0

def nqueen(k, board, y):
    global cnt
    if k==n:
        cnt+=1
        return
    
    for i in y:
        valid = 1 #True
        for idx, t in enumerate(board): #board가 비어있으면 실행X
            if t+k-idx == i or t-k+idx==i:
                valid = 0 #False
                break
                
        if valid:
            idx = y.index(i)
            nqueen(k+1, board+[i], y[:idx]+y[idx+1:])

#board = []
#i번째 행의 퀸이 몇 번째 열에 있는지 표시
nqueen(0, [], [i for i in range(n)])
print(cnt)

 

짧은 풀이

• board 리스트를 2차원으로 구성하지 않고 1차원으로 하였다. i번째 행의 퀸이 몇 번째 열에 있는지 표시하면 된다.
• y 리스트를 넘김으로써 한 번 선택된 열의 모든 원소는 이후에 고려되지 않고 넘길 수 있도록 하였다.
  • y 리스트 속 원소를 삭제하여 반복문을 돌리면 당연히 해당 원소는 스킵된다.
• 리스트가 변형되지 않고 반복문이 진행되어야 한다. deepcopy()를 사용하지 않고 하려면
  • 리스트에 append()를 사용하지 않고, 함수 호출 시에 바로 extend(+)를 이용하여
    • 마지막 원소를 덧붙이거나, 원하지 않는 원소만 슬라이싱으로 제외하여 재귀를 진행했다.

• Pypy3로 해야 맞는다......

# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean
n = int(input())
k = int(input())
b = [ [0]*n for _ in range(n)]
xx = list(map(int,input().split()))
yy = list(map(int,input().split()))
for x,y in zip(xx,yy):
	b[x-1][y-1] = -1

board=[]
cnt = 0
visit = [0]*(n)

def nqueen(k):
	global cnt,board
	if k==n:
		cnt+=1
		return
	
	for i in range(n):
		if visit[i]==0:
			valid = True
			# y = ax+b  -> b = y-x
			# y = -ax+b -> b = y+x
			for idx, t in enumerate(board): # 대각선 감지
				if t+(k-idx)==i or t-(k-idx)==i:
					valid = 0
					break
			
			if valid and b[k][i] != -1:
				board.append(i)
				visit[i]=1
				nqueen(k+1)
				visit[i]=0
				board.pop()

nqueen(0)
	
print(cnt)

 

시간 초과 -> deepcopy()를 사용하지 않고 할 수 있는 방법이 없을까

(답은 맞다...)

import copy
n = int(input())


# 0 = empty, -1 = cannot, 1 = queen

dy = [1,-1]

cnt = 0
def nqueen(k,board,y):
    global cnt
    if k==n:
        #print("cnt: ",cnt)
        #for x in board:
        #    print(x)
        #print()
        cnt+=1
        return 
    old_board = copy.deepcopy(board)#board.copy()
    for i in y:
        if board[k][i]==0:              
            for z in range(2):
                for t in range(1,n-k):
                    nx, ny = k+t,i+t*dy[z]
                    if 0<=nx<n and 0<=ny<n:
                        if board[nx][ny] != 1:
                            board[nx][ny] = -1
                        else: break
                        
            
            board[k][i] = 1
            #print(k,y)
            idx = y.index(i)
            #for x in board:
            #    print(x)
            #print()
            nqueen(k+1,board,y[:idx]+y[idx+1:])
        board = copy.deepcopy(old_board)#old_board.copy()
    

def solution():
    board = [[0 for _ in range(n) ] for _ in range(n)]
    y = [i for i in range(n)]
    nqueen(0,board,y)
solution()
print(cnt)