9663. N-Queen

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
10 초	128 MB	137940	67033	43011	46.900%

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

풀이

실패: 시간초과

def n_queen(x, y):  
	# 부분1
    if checkY[y] == 1: return 0  
    if (addList[x+y] == 1): return 0  
    if (minusList[x-y+N] == 1): return 0  
 
	# 부분 2
    cnt = 0  
    queens[x][y] = 1  
    checkY[y] = 1  
    addList[x+y] = 1  
    minusList[x-y+N] = 1  
 
	# 부분 3
    if x == N-1:  
        addList[x + y] = 0  
        minusList[x - y + N] = 0  
        checkY[y] = 0  
        queens[x][y] = 0  
        return 1  
	# 부분 4
    for i in range(N):  
        cnt += n_queen(x+1, i)  
	
	# 부분 5
    checkY[y] = 0  
    addList[x + y] = 0  
    minusList[x - y + N] = 0  
    queens[x][y] = 0  
    return cnt  
  
N = int(input())  
queens = [[0 for _ in range(N)] for _ in range(N)]  
checkY = [0 for _ in range(N)]  
addList = [0 for _ in range(2*N)]  
minusList = [0 for _ in range(2*N)]  
  
sum = 0  
for y in range(N):  
    sum += n_queen(0,y)  
print(sum)

• n_queen(x, y): 주어진 x, y값에 queen을 놓을 수 있는 지 없는 지를 판별하고, 놓을 수 있다면 다음 줄로 넘어감.

  • 부분 1: x, y값에 queen을 놓을 수 없으면 return 0
  • 부분 2: x, y에 queen 놓기
  • 부분 3: 만일 마지막 줄인 경우, 놓았던 queen을 되돌리고 return 1
  • 부분 4: 다음 줄에 처음부터 끝까지 queen을 배치해보기 위해 n_queen() 재귀호출하고 호출의 return 값을 cnt에 누적
  • 부분 5: 놓았던 queen을 되돌리고 누적된 cnt를 반환.

• 실패 원인: 함수 호출이 너무 많음

성공

def n_queen(i):  
    if (i == N): return 1  
    cnt = 0  
    for j in range(N):  
        if checkCol[j] == 0 and checkDiagAdd[i+j] == 0 and checkDiagMinus[i-j+N] == 0:  
            checkCol[j] = checkDiagAdd[i+j] = checkDiagMinus[i-j+N] = 1  
            cnt += n_queen(i+1)  
            checkCol[j] = checkDiagAdd[i+j] = checkDiagMinus[i-j+N] = 0  
    return cnt  
  
N = int(input())  
checkCol = [0] * N  
checkDiagAdd = [0] * (2*N)  
checkDiagMinus = [0] * (2*N)  
print(n_queen(0))

• 수정

  1. 굳이 체스판(queens)을 사용할 필요 없어서 제거 → 이미 필요한 정보는 다른 배열들에 저장되어있음
  2. 함수 n_queen()의 역할이 살짝 수정됨
     1. 해당 줄(i)에 각 칸에 퀸을 넣을 수 있는지 없는지를 판별하고 다음 줄로 넘어감
     2. 기준이 칸이 아니라 줄로 변경되어 함수 호출 횟수가 줄어듬.
     3. 줄 기준이 가능 한 이유는 줄별로 무조건 1개의 queen만을 놓아야하기 때문임.
  3. 2번으로 인해 함수 n_queen()이 필요로하는 매개 변수가 x, y 두 개에서 i한개로 변함.

• 풀이

  • n_queen()의 역할: 해당 줄(i)의 특정 칸 (j)에 queen을 놓을 수 있는 지 판별
    • 만일 끝까지 queen을 놓으면서 끝에 도달했다면, 1을 반환 → if (i == N): return 1
    • 아직 끝이 아니라면 각 칸별로 놓을 수 있는지 판별 → if checkCol[j] == 0 and checkDiagAdd[i+j] == 0 and checkDiagMinus[i-j+N] == 0:
    • 놓을 수 있다면
      • 놓은 후 → checkCol[j] = checkDiagAdd[i+j] = checkDiagMinus[i-j+N] = 1
      • 다음 줄(i+1)로 넘어가 같은 작업 반복 → cnt += n_queen(i+1)
      • 완료하고 받아온 return값을 cnt에 저장하고
      • 놓았던 queen을 회수함 → checkCol[j] = checkDiagAdd[i+j] = checkDiagMinus[i-j+N] = 0 #Computer #PS