글 읽기 - 코린이 N -Queen 살려주십쇼ㅠ ㅠㅠㅠㅠ

tpgud10 1년 전 0

코린이 좀 구해주세요 어디가 틀린 것인지 지적해주시면 감사하겠습니다 ㅠㅠㅠㅠㅠㅠ

# Queen 은 같은 index 를 가질 수도, 같은 줄에 있을 수도 없다.
# # 대각선도 안됨.
n = int(input())
# 체스판 한 줄
chess = []
for i in range(n):
    chess.append(True)
# # 체스판
all = []
for j in range(n):
    all.append(chess)

cnt = 0
# # 경우의 수를 탐색
def dfs(depth): # idx 는 각 줄을 의미
    global all, cnt
    if depth == n :
        cnt += 1
        return

    # Queen이 각 줄에서 올 수 있는 경우의 수
    for i in range(n): # i 는 row 의 인덱스 을 의미한다.
        if all[depth][i] == True:     # depth 줄의 i 번째 index 가 기준이 된다.
            for j in range(depth, n): # j 지울려고 하는 row
                all[j][i] = False     # 같은 세로 줄
                if i + j - depth < n:
                    all[j][i + j - depth] = False  # 대각선 오른쪽
                if i - j + depth >= 0:
                    all[j][i - j + depth]  = False # 대각선 오른쪽
            dfs(depth + 1)
            
dfs(0)
print(cnt)

siyamaki 1년 전 0

Queen의 특성을 이용하여 map의 i,j를 전부 확인하지 않고 X축, Y축 방문 체크하는 1차원배열 2개로 체크해보세요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

코린이 N -Queen 살려주십쇼ㅠ ㅠㅠㅠㅠ

tpgud10 1년 전 0

siyamaki 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말