[SWEA] 2806_N-Queen

📕 문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB&categoryId=AV7GKs06AU0DFAXB&categoryType=CODE&problemTitle=2806&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1&&&&&&&&& 

SW Expert Academy

 

💡 풀이법

1. dfs함수에서 r은 현재 행의 위치, queens는 현재까지 퀸을 둔 열의 리스트이다.

2. is_available함수는 지금 선택한 열(candidate)에 퀸을 위치시켰을 때 현재 퀸이 이전에 둔 퀸에게 공격을 받는지 안받는지를 판별하는 함수이다.

3. 0행일때는 이전에 둔 퀸이 없기 때문에 모든 열에 대해 dfs 함수가 실행이 된다.

(이때, r은 +1을 하면서 dfs를 실행한다.)

4. 퀸을 둔 열을 queens라는 리스트에 계속 추가해나간다.

5. 1행부터는 이전에 둔 퀸의 위치가 queens에 저장이 되어있기 때문에 비교하면서 둘 수 있는 열에 대해서만 dfs를 실행한다.

(이때, r은 +1을 하면서 dfs를 실행한다.)

6. r이 N이면 모든 행에 퀸을 둔 상태라는 뜻이므로 이때는 경우의수(ans)를 +1 해준다.

 

def is_available(candidate, row, col):
    for i in range(len(candidate)):
        if candidate[i] == col or abs(candidate[i] - col) == row - i:
            return False
    return True

def dfs(r, queens):
    global ans

    if r == N:
        ans += 1
        return

    for i in range(N):
        if is_available(queens, r, i):
            queens.append(i)
            dfs(r+1, queens)
            queens.pop()

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    ans = 0
    dfs(0, [])
    print('#{} {}'.format(tc, ans))