[백준] 9663 : N-Queen

문제

개념

백트래킹

재귀를 이용해야 한다.
반복문이 가지 뻗듯이 많이 생길 것 같은 문제

백트래킹 풀이 방법

• 재귀 함수의 종료 시점 부터 지정한다.
• 대체로 종료 시점 지정 후 for문이 등장한다.
• for문 안에 각각의 경우에 대해 값을 바꿔가며 재귀함수를 호출한다.
• 시간 초과를 막기 위해 모든 for문을 돌지 않고, 특정 경우에만 실행하도록 가지치기를 하기도 한다.

백트래킹의 기본 재귀 함수

def backtracking(loc, ...):
	# 종료를 위한 조건문 
	if ...: 
    	return 
    
    # 현재 위치 부터 for문
    for i in range(loc, ...): 
    	backtracking(i+1, ...) 
    return

백트래킹에서 헷갈리는 인덱스

• 문제에 따라서 해줘야하는 인덱스 처리가 다 다르다.
• 시작점이 정해져 있는게 아니라면 backtracking에 넣는 값은 loc로 구한 값이 아니라 i로 구한 값이어야 한다.
• backtracking함수를 재귀 호출할 때, loc는 이미 포함한 값이 아니라 이 다음에서 접근할 값의 시작이다. 따라서 backtracking(i+1, 뒤에 변수는 i를 이용해서 구한 값)

Source : https://juhi.tistory.com/15

풀이 1

참고한 블로그
https://0giru.tistory.com/38
(설명 매우 자세)

https://junior-datalist.tistory.com/89

n = int(input())
result = 0
graph = [0 for _ in range(n+1)] 
# i 는 행(row), graph[i]는 열(col) (각 행에 있는 위치(i)를 graph[i]라는 원소값으로 표시)
# n개의 열

# 모든 퀸은 한 행에 한개씩 들어가기 때문에 행검사는 할 필요 없다
# 열 검사와 대각 검사만 하면 됨
# 위에서부터 차례로 내려오기 때문에 해당 row 전까지만 검사하면 된다

# 백트랙킹을 위한 검사함수
# col에는 가능한 col후보가 들어감
def promising(graph, row, col):
    # 열 검사
    for i in range(1, row): # 이전 행에서 현재 행까지 점유되었는지만 검사하면 됨
        if graph[i] == col: # 현재 검사하려는 열이 점유되었는지 검사
            return False # False 반환하고 함수 종료
    
    # 대각 검사
    for i in range(1, row):
        # 두 퀸의 행의 차와 열의 차의 크기가 같다면, 두 퀸은 대각선상에 존재하게 됨
        if abs(graph[i] - col) == row - i:
            return False
    
    return True # 둘 다에 해당되지 않으면 True 반환

# 검사 결과에 따라 다음 행을 검사하거나 이전 행으로 되돌아감
def nqueen(graph, row, num):
    global result
    
    if row == num + 1: # 하나씩 더해진 행이 입력받은 행의 수와 동일할 때 (첫 행을 1로 설정해서 num + 1이 총 행의 갯수)
        result += 1 # N개의 행을 모두 검사하면 재귀 종료
        return
    
    # 1 ~ n까지의 col(열) 후보 중 가능한 후보를 판별
    for col in range(1, n+1):
        if promising(graph, row, col): # 열과 대각에 모두 위치할 수 있는 열, 위치(열과 대각 모두 True나온 것)
            graph[row] = col # 해당 행에 열 정보를 입력
            nqueen(graph, row+1, num) # 다음 행 검사 시작
        else:
            continue # 열과 대각에 위치할 수 없으면 다음 열 검사
        


nqueen(graph, 1, n) # 첫 행을 1로 둠
print(result)

시간초과 풀이

import sys

n = int(sys.stdin.readline())

pos = [0] * n
f_a = [False] * n
f_b = [False] * (2*n-1)
f_c = [False] * (2*n-1)

c = 0

def set(i, n):
    global c
    for j in range(n):
        if ( not f_a[j]            # j행에 퀸이 배치 되지 않았다면
            and not f_b[i + j]        # 대각선 방향(↙↗)으로 퀸이 배치 되지 않았다면
            and not f_c[i - j + (n-1)]):
            pos[i] = j  # 퀸을 j행에 배치
            if i == n-1:  # 모든 열에 퀸을 배치하는 것을 완료
                c += 1
               
            else:
                f_a[j] = f_b[i + j] = f_c[i - j + (n-1)] = True
                set(i + 1, n)  # 다음 열에 퀸을 배치
                f_a[j] = f_b[i + j] = f_c[i - j + (n-1)] = False
            
    return c

print(set(0, n))

정답 풀이

pypy로 제출했을 때 맞음!

import sys

n = int(sys.stdin.readline())
mlist=[0]*n

def check(mlist, row): # 백트래킹
    for i in range(row):
        if mlist[i] == mlist[row] or abs(mlist[row]-mlist[i]) == row - i:
            return False # 방문할 수 없는 경우이므로 False 주기
    return True

def search(mlist, row):
    count = 0
    if n == row:
        return 1
    
    for col in range(n):
        mlist[row] = col
        if check(mlist, row): # 퀸들이 이동할 수 없을 경우엔 다음 컬렴 (백트래킹)
            count += search(mlist, row+1)
    
    return count

print(search(mlist, 0))

스스로 풀어본 풀이

이번에는 행(row)이 아니라 열(col)을 기준으로 둘 때로 풀어보았다.
for문으로는 그 다음 행으로 가는 거고
재귀로는 다음 열로 가는 것!

import sys

# 이번에는 열을 기준으로 N-Queen 문제 풀어보기
n = int(sys.stdin.readline())
count = 0
arr = [0 for i in range(n)] # ex. arr[0] = 4 라고 하면 0열 4행에 퀸이 있는 것

def check(col):
    for i in range(col): # 처음에 n으로 뒀었음
        # if col != i: # col 자기 자신을 제외하고 비교해준다고 생각했으나, 재귀 때문에 열이 하나씩 더해지기 때문에 for i in range(row)로 둬야!
            if arr[col] == arr[i] or abs(arr[col]-arr[i]) == col - i: # i가 col 미만까지 돌기 때문에 col - i는 양수일 수밖에 없음!
                return False # 방문할 수 없으면 False 반환
    return True # 방문할 수 있으면 True 반환
            

def queen(col):
    global n, count, arr
    
    if col == n:
        count += 1
        return
    
    for i in range(n):
        arr[col] = i
        if check(col):
            queen(col+1)
            arr[col] = 0 # 재귀 끝난 후, arr[col]을 0으로 리셋해줌 // 처음에 arr = [0 for i in range(n)]해줬다가 틀림!


queen(0)
print(count)

22.05.06

import sys
input = sys.stdin.readline

n = int(input())
board = [0 for _ in range(n)] 
# board[열(col)] = 행(row) 
# 열이 인덱스 역할

def check(col): # 해당 열의 행에 둘 수 있는지 확인
    for i in range(col):
        if board[i] == board[col] or abs(board[i]-board[col]) == col - i:
            return False
    return True # return 위치 실수했었음!!!

def dfs(col): # 현재 열
    count = 0
    if col == n: # 현재 열이 끝에 도달했을 때
        return 1
    
    for row in range(n): # 하나의 col에 n개의 row를 모두 위치시켜봄
        board[col] = row # 여기서 board[col] = row로 초기화해준 값을 가지고
        if check(col):   # check(col)에서 놓을 수 있는지 확인해보는 것!
            count += dfs(col + 1) # 해당 행에 놓을 수 있다면 다음 열로 재귀 탐색
    
    return count
    
print(dfs(0))

'''
visited 처리 필요 없는 이유
board 배열에 값을 갱신하면서 더해주거나 빼주는 구조가 아니라, 
재귀가 한 번 돌 때마다 board[col] = row 로 값을 새롭게 대입해주는 방식이기 때문

또한 구해야 하는 값인 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수는 
변수 count 에 계속 쌓이고 있음
'''