[SWEA] 파이썬 2806. N-Queen | 백트래킹(Backtracking)

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB 

SW Expert Academy

 

 

문제 해결 포인트

- 전형적인 Backtracking 문제 (DFS에서 가지치기)

- 트리 구조를 생각하면서 깊이가 곧 보드의 행이고 해당 행에서 배치 가능한 열을 찾는 것이다.

 

- 위 그림은 3 x 3 보드 일 때의 탐색을 시각화 한 모습이다.

- X 표시는 promisiong에 걸려서 더 이상 깊이 탐색하지 않고 넘어간다.

- DFS(3) 이라면 모든 행의 퀸 자리가 알맞은 경우이므로 카운트해준다. 

 

 

- 같은 열에 있거나 같은 대각선에 있는 경우 해당 경우에 대해 더이상 탐색하지 않는다.

   ㄴ 두 점이 각각 (x1, y1), (x2, y2) 이고,  | x1 - x2 | = | y1 - y2 |  일 때 같은 대각선에 있다 (same diagonal)

 

 

작성 코드

 

def promising(row):
    for i in range(row):
        if column[row] == column[i] or row - i == abs(column[row] - column[i]):
            # 퀸이 같은 대각선 또는 열에 존재한다면 탐색 중지
            return False
    return True


def dfs(row):
    global result
    if row == n:  # n 번째 행 퀸까지 결정 됐다면
        result += 1
    else:
        for col in range(n):  # row 행의 어느 열
            column[row] = col  # 퀸 배치
            if promising(row):  # (Backtracking) 더 탐색할지 결정
                dfs(row+1)


for test in range(1, int(input())+1):
    n = int(input())  # n * n 보드
    column = [-1]*n  # i번째 행에 위치한 퀸의 열 위치
    result = 0

    dfs(0)

    print("#{} {}".format(test, result))

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚