백준 9663번 N-Queen 파이썬

2023-01-18, 2023-01-19

백준 9663번 N-Queen 파이썬

참고: https://chanhuiseok.github.io/posts/baek-1/
https://seongonion.tistory.com/103
https://www.acmicpc.net/problem/9663

무엇?

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

왜?

정글 알고리즘 주차때 못 풀었거나 & 정답을 참고해서 풀었던 문제들 다시 풀기

어떻게?

내 코드

• 백트래킹 (dfs에 조건을 걸어 경우의 수를 제한하는 방법)

# https://www.acmicpc.net/problem/9663
# N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제

import sys

def promising(r):
    for i in range(r):
        if edges[r] == edges[i]:
            return False
        elif (abs(r-i)) == (abs(edges[r]-edges[i])):
            return False
    return True

def dfs_visit(r: int):  # r == 퀸을 두기 위해 탐색하는 행
    global count
    if r == N:
        count += 1
        return
    # 지금까지 두었던 자리들과 비교
    for col in range(N):    # 컬럼 탐색
        edges[r] = col
        if promising(r) == True:
            dfs_visit(r+1)

N = int(sys.stdin.readline())
count = 0
edges = [-1] * N  # -1로 초기화

dfs_visit(0)

print(count)

try-error

1. promising() 함수를 지정하지 않고 일반 반복문으로 해결하려고 했을 때 한계가 있음 → 두면 안될 곳을 완전히 기억하지 못함.

# 수정 전 코드
def dfs_visit(r: int, edges: list):  # r == 퀸을 두기 위해 탐색하는 행
    global count
    if r == N:
        count += 1
        return
    # 지금까지 두었던 자리들과 비교
    for col in range(N):    # 컬럼 탐색
        edges[r] = col
        for i in range(r):
            positioned = edges[i]
            if col == positioned:
                break #### 여기서 return False 한 것처럼 완전 반복문을 탈출해야 함 
            elif (abs(r-i)) == (abs(col-positioned)):
                break #### 여기서 return False 한 것처럼 완전 반복문을 탈출해야 함 
        dfs_visit(r+1, edges)

promising 한 지 판단할 때 완전히 걸러지지 않고, 불필요하게 시간을 낭비하게 됨
따라서 promising 함수 지정해서 하는 게 낫다.

2. dfs(), dfs_visit() 두 개로 했을 때 시간초과 안나지만, 굳이 필요 없어서 지워도 됨.

# 수정 전 코드
def dfs(N):  
    for c in range(N):
        edges[0] = c  
        dfs_visit(1)  

3. promising() 함수에서 다음과 같이 하면 시간초과로 실패함

# 수정 전 코드
def promising(r):
    for i in range(r):
        col = edges[r]  #### 이 줄과 아래 줄을 살리면 시간초과?!
        positioned = edges[i]
        if edges[r] == edges[i]:
            return False
        elif (abs(r-i)) == (abs(edges[r]-edges[i])):
            return False
    return True

아마 이미 시간이 오래 걸리는 알고리즘이고, 한끗 차이로 실패하는 것 같다 … ?

정답 예시

• dfs에서 set를 이용한 방법

import sys
input = sys.stdin.readline

n = int(input())
count = 0
row = set()
pos_diag = set()
neg_diag = set()
dp = [0] * n

def dfs(x):
    global row, pos_diag, neg_diag, count
    if x == n:
        count += 1
        return
    for i in range(n):
        if i in row:
            continue
        if i-x in pos_diag:
            continue
        if i+x in neg_diag:
            continue
        dp[x] = i
        # set에 불가능한 자리의 경우의 수를 추가
        row.add(i) 
        pos_diag.add(i-x)
        neg_diag.add(i+x)
        dfs(x + 1)
        # 리턴하면서 원소 제거 
        row.remove(i)
        pos_diag.remove(i-x)
        neg_diag.remove(i+x)

dfs(0)
print(count)

나와 다른 점

1. set 사용
   위 try-error에서도 언급했지만, 나도 반복문을 사용했다가 조건을 완전히 기억하지 못하는 에러가 있어서 함수를 사용하도록 바꿨다.
   갈 수 없는 지점을 리스트에 저장하는 방법을 생각했었지만 탐색 시간이 너무 오래 걸릴 것 같아서 그렇게 하지 않음.
   set를 이용하면 탐색에 걸리는 시간이 O(1)이니, 위에서 언급한 문제를 해결해 줄 수 있다.
2. 반복문 사용
   처음에 나도 반복문으로 해결하려고 했는데 1에서 언급한 문제 때문에 함수 정의로 전회.
   반복문이 좀 더 시간이 빠르게 나올 듯.