[9663번] n-Queen with Python (★)

문제

 

참고한 코드

import sys
# pypy3 해결.. python(3%) 시간초과


# 대각선의 퀸이 있는지 확인
def check(x):
    for i in range(x):
        if abs(graph[x] - graph[i]) == x - i:
            return False
    return True


# 체스 판의 열을 dfs 탐색
def dfs(queen):
    global res

    # n번째 퀸을 놓으려 한다면 리턴 (n개의 퀸을 놓았기 때문.)
    if queen == n:
        res += 1 # 방법의 수 카운트
        return

    # 모든 체스판의 열을 확인
    for i in range(n):
        # i 번째 열의 퀸을 놓지 않았다면
        if not visited[i]:
            graph[queen] = i # (queen, i)에 퀸을 둔다.

            # 대각선의 겹치는 퀸이 있는지 확인
            if check(queen):
                # 백 트래킹
                visited[i] = True # 퀸을 놓는다.
                dfs(queen + 1) # 재귀적으로 퀸을 놓을 수 있는 열을 찾는다.
                visited[i] = False # 재귀 탐색 후 퀸을 n개 놓을 수 없다면 퀸을 놓지 않는 것으로 초기화 후 다른 열을 탐색


n = int(sys.stdin.readline())
graph = [0 for _ in range(n)] # n번째 열의 퀸의 위치
visited = [False for _ in range(n)] # 체스판의 탐색 여부
res = 0 # 퀸을 놓는 방법의 수

dfs(0)
print(res)

> 참고한 블로그

https://fre2-dom.tistory.com/247

[baekjoon] 백준 9663번(파이썬): N-Queen

> 와.... 진짜 어렵다 ㅜㅜ

 

내가 해석한 코드 설명

def check(x):
    for i in range(x):
        if abs(graph[x] - graph[i]) == x - i:
            return False
    return True

> 이 코드는 대각선의 퀸이 있는지 확인하는 코드이다. 일단 퀸은 상하좌우 대각선 모두 움직일 수 있다.

> for문을 사용해서 x의 길이만큼 반복문을 진행한다.

> abs(graph[x] - graph[i]) == x - i 의 의미는 두 값이 같게 된다면 대각선이라는 의미이다. 솔직히 아직도 이해가 잘안됐닼ㅋㅋ

> 반복문을 통과한다면 True, 아니면 False

 

# 체스 판의 열을 dfs 탐색
def dfs(queen):
    global res

    # n번째 퀸을 놓으려 한다면 리턴 (n개의 퀸을 놓았기 때문.)
    if queen == n:
        res += 1 # 방법의 수 카운트
        return

    # 모든 체스판의 열을 확인
    for i in range(n):
        # i 번째 열의 퀸을 놓지 않았다면
        if not visited[i]:
            graph[queen] = i # (queen, i)에 퀸을 둔다.

            # 대각선의 겹치는 퀸이 있는지 확인
            if check(queen):
                # 백 트래킹
                visited[i] = True # 퀸을 놓는다.
                dfs(queen + 1) # 재귀적으로 퀸을 놓을 수 있는 열을 찾는다.
                visited[i] = False # 재귀 탐색 후 퀸을 n개 놓을 수 없다면 퀸을 놓지 않는 것으로 초기화 후 다른 열을 탐색

> res 변수는 경우의 수를 알려주는 결과값 변수이다.

> 어렵다 ㅜㅜ