9663. N-Queen

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

 

 

앞선 문제인 N과 M에서 사용되는 DFS를 활용한 문제이다.

중요한 아이디어는 같은 row에는 퀸이 하나밖에 존재할 수 없으며, 또 하나는 무조건 있다는 것이다.

이번 row에는 퀸이 어디에 와야할 지 column을 차례대로 늘려가면서 findColumn 함수를 통해 검사한다.

개인적으로는 row와 col이 서로 헷갈리고, for문의 range를 정하는 것 때문에 어려웠던 문제이다.

 

코드 설명은 주석으로 대신한다. 밑에서부터 보면 된다.

def isPossible(row, col):  # 위 혹은 양방향 대각선에 퀸이 있는지 검사
    # 좌우는 볼 필요가 없다. 하나의 row에는 하나의 퀸!

    # 위 (아래를 안 보는 이유는 아직 다음 row 자체를 안 봤기 때문
    for i in range(1, n):  # 주의: 1부터다. 0으로하면 7번째 줄에서 자기 자신과 같은지 검사하게 됨
        if row-i >= 0:  # row를 1씩 줄여가되 음수가 되지 않도록 한다. 
            if chess[row-i][col]:  # 퀸을 발견했다
                return False

    # \ 방향 대각선. row, col에서 1씩 빼면서 확인
    for i in range(1, n):
        if row-i >= 0 and col-i >= 0:
            if chess[row-i][col-i]:
                return False

    # / 방향 대각선. row는 -1, col은 +1 (그림으로 생각해보자)
    for i in range(1, n):
        if row-i >= 0 and col+i < n:
            if chess[row-i][col+i]:
                return False
    return True  # 위 모든 검사를 통과했다면 그거슨 퀸

def findColumn(row):
    global answer  # 전역변수를 함수 내에서 수정하기 위해 global 선언
    if row == n:  # 하나의 row에는 하나의 퀸이 무조건 들어가므로, row가 n이라면 퀸의 자리를 다 찾은 것임
        answer += 1
        return
    for col in range(n):  # row는 정해져 있으니 column을 1씩 증가시키면서 확인한다
        if isPossible(row, col):  # 놓을 수 있다면 
            chess[row][col] = True  # True로 퀸의 자리를 표시
            findColumn(row+1)  # 다음 row에서 퀸의 자리를 찾는다
        chess[row][col] = False  # 재귀가 끝난 후, 백트래킹해야하므로 다시 False로 돌려놓는다

n = int(input())
chess = [[False]*n for _ in range(n)]  # 체스판. True면 퀸이 있는 자리
answer = 0
findColumn(0)  # 인자는 row. 0번째 row부터 퀸이 들어갈 column을 찾는다.
print(answer)