[백준] 9663. N-Queen

 

📌문제

https://www.acmicpc.net/problem/9663

 

🎖️난이도

 

✔️풀이

# sol1) 재귀
# python3 오답 (시간 초과) & pypy3 정답 (30044ms)

n = int(input())
queen = [0 for _ in range(n)] # 각 행마다의 퀸의 위치(열)
cnt = 0

# 해당 행에 퀸을 놓을 수 있는 곳이 있는지(유망한지) 현재 queen 배열 상태 체크
def isPromising(row):
    # 체크하려는 행의 이전 행까지만 체크
    for i in range(row):
        # 퀸을 놓을 수 없는 경우 2가지 (유망 x)
        # 1. 같은 열에 위치한 퀸이 있거나 or 2. 왼쪽 위 or 오른쪽 위 대각선에 퀸이 있거나
        if queen[row] == queen[i] or abs(queen[row] - queen[i]) == row - i:
            return False
    return True

# 행 단위로 퀸 추가
def dfs(row):
    # 마지막 행까지 모두 유망해서 퀸을 둘 수 있었다면 (퀸 총 n개 모두 두기 성공)
    if row == n:
        global cnt # 전역 변수 접근
        cnt += 1
        return
    
    # 각 행에서 열 단위로 퀸 이동 (모든 열 중에 배치 가능한 곳이 있는지 체크)
    for col in range(n):
        queen[row] = col # [row][col]에 퀸 배치 (0->1->2->3 위치로 이동)
        if isPromising(row):
            dfs(row+1) # 다음 행으로 ㄱㄱ
            
dfs(0)
print(cnt)

 

# sol2) 재귀 + visited
# python3 오답 (시간 초과) & pypy3 정답 (13428ms)

n = int(input())
queen = [0 for _ in range(n)] # 각 행마다의 퀸의 위치(열)
visited = [False for _ in range(n)]
cnt = 0

# 해당 행에 퀸을 놓을 수 있는 곳이 있는지(유망한지) 현재 queen 배열 상태 체크
def isPromising(row):
    # 체크하려는 행의 이전 행까지만 체크
    for i in range(row):
        # 퀸을 놓을 수 없는 경우 2가지 (유망 x)
        # 1. 같은 열에 위치한 퀸이 있거나 or 2. 왼쪽 위 or 오른쪽 위 대각선에 퀸이 있거나
        if queen[row] == queen[i] or abs(queen[row] - queen[i]) == row - i:
            return False
    return True

# 행 단위로 퀸 추가
def dfs(row):
    # 마지막 행까지 모두 유망해서 퀸을 둘 수 있었다면 (퀸 총 n개 모두 두기 성공)
    if row == n:
        global cnt # 전역 변수 접근
        cnt += 1
        return
    
    # 각 행에서 열 단위로 퀸 이동 (모든 열 중에 배치 가능한 곳이 있는지 체크)
    for col in range(n):
        
        # ***중복 방문 제거!!***
        if visited[col]:
            continue
        
        queen[row] = col # [row][col]에 퀸 배치 (0->1->2->3 위치로 이동)
        if isPromising(row):
            visited[col] = True
            dfs(row+1) # 다음 행으로 ㄱㄱ
            visited[col] = False
            
dfs(0)
print(cnt)